#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

using namespace std;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    vector<ll> siz(100);
    vector<int> even(0);
    vector<int> odd = {1};
    siz[1] = 1;
    rep(i,2,100){
        vector<int> targ;
        if (i & 1){
            targ = even;
        }else{
            targ = odd;
        }
        int memo = -1;
        int num = 0;
        vector<int> ret;
        auto add = [&]() -> void {
            if (num > 0){
                vector<int> a;
                while(num > 0){
                    a.push_back(num % 2);
                    num /= 2;
                }
                reverse(all(a));
                for (int j: a) ret.push_back(j);
                ret.push_back(memo);
            }
        };
        rep(j,0,(int)targ.size()){
            if (memo != targ[j]){
                add();    
                memo = targ[j];
                num = 1;  
            }else{
                num++;
            }
        }
        if (num > 0) add();
        if (i & 1){
            odd = ret;
            siz[i] = odd.size();
        }else{
            even = ret;
            siz[i] = even.size();
        }
        if (odd.size() > 1111111 && even.size() > 1111111){
            reverse(all(odd));
            reverse(all(even));
            odd.resize(1100000);
            even.resize(1100000);
            siz.resize(i + 1);
            break;   
        }
    }

    int t; cin >> t;
    while(t--){
        ll n; int m; cin >> n >> m;
        if (n < (ll)siz.size() && siz[n] <= m){
            cout << 0 << '\n';
        }else{
            if (n & 1){
                cout << odd[m] << '\n';
            }else{
                cout << even[m] << '\n';
            }
        }
    }
}