#include <bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
#define all0(x) (x).begin(), (x).end()
typedef long long LL;

void solve() {
    // LL n, m; cin >> n >> m;
    V<V<int>> bef(1);

    V<int> a(1, 1);
    V<int> pa;
    auto gen = [&](V<int>&a, int x) -> void {
        for(int i = __lg(x); i >= 0; i--) {
            a.pb(x >> i & 1);
        }
    };
    V<int> odd, even;
    int n = 1;
    int t = 40;
    bef.pb(a);
    while(t) {
        t--;
        pa = a;
        a.clear();
        for(int i = 0; i < pa.size(); i++) {
            int r = i;
            while(r < pa.size() && pa[r] == pa[i]) {
                r++;
            }
            r--;
            gen(a, r - i + 1);
            a.pb(pa[i]);
            i = r;
        }
        n++;
        reverse(all0(a));
        a.resize(min((int)a.size(), (int)1e6));
        reverse(all0(a));
        bef.pb(a);
        if(a.size() == 1e6) {
            if(n & 1) {
                odd = a;
            } else {
                even = a;
            }
        }
    }

    cin >> t;
    while(t--) {
        LL n, m; cin >> n >> m;
        m++;
        if(n <= 40) {
            if(m > bef[n].size()) cout << 0 << endl;
            else cout << bef[n][bef[n].size() - m] << endl;
        } else {
            if(n & 1) cout << odd[odd.size() - m] << endl;
            else cout << even[even.size() - m] << endl;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // int t;
    // std::cin >> t;

    // while (t--) {
    //     solve();
    // }
    solve();
}