//
//  na 2377.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/19.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef __int128 lll;
typedef long long int ll;
typedef unsigned long long int ull;
const ull ullinf = 0xffffffffffffffff;
ll m;
int k;
vector<lll> kvs[4];
inline void init(){
    for(int i = 0; i <= 64; ++i)
        kvs[1].push_back(lll(1) << i);
    for(int i = 0; i <= 64; ++i)
        for(int j = 0; j < i; ++j)
            kvs[2].push_back((lll(1) << i) | (lll(1) << j));
    for(int i = 0; i <= 64; ++i)
        for(int j = 0; j < i; ++j)
            for(int k = 0; k < j; ++k)
                kvs[3].push_back((lll(1) << i) | (lll(1) << j) | (lll(1) << k));
}
#define ceilhalf(x) ((x >> 1) + (x & 1))
inline void smallk(){
    lll l, r;
    ull ans = 0;
    vector<lll> &vs = kvs[k];
//    cerr << "vs = " << endl;
//    for(int i = 0; i < 10; ++i)
//        cerr << "     " << ull(vs[i]) << endl;
    int len = int(vs.size());
    bool finmin = false;
    if(m <= len + 1){
        for(int i = int(m) - 1; i < len; ++i){
            r = vs[i - m + 1] - 1;
            l = ceilhalf(vs[i]);
            if(i != m - 1)
                l = max(l, vs[i - m]);
            if(i != len - 1)
                r = min(r, (vs[i + 1] >> 1) - (~vs[i + 1] & 1));
            else if(r > ullinf)
                r = ullinf;
            if(l <= r){
//                cerr << ull(l) << " -> " << ull(r) << endl;
//                cerr << "choosing " << ull(vs[i - m + 1]) << " -> " << ull(vs[i]) << endl;
                ans += r - l + 1;
                if(!finmin){
                    finmin = true;
                    cout << ull(l) << ' ';
                }
            }
        }
    }
    cout << ans << endl;
}
inline void smallm(){
    cout << "NVM TOO COMPLICATED" << endl;
}
inline void solve(){
    cin >> m >> k;
    if(k <= 3){
        smallk();
    }else if(m <= 10){
        smallm();
    }else{
        cout << "Passed" << endl;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    init();
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}