#include <bits/stdc++.h>
using namespace std;

#define ar array
#define F first
#define S second
typedef int uci;
#define int long long

vector<bool> bin(int x) {
    vector<bool> res;

    bool start = false;
    for (int k = 30; k >= 0; k--) {
        if (x>>k&1) {
            start = true;
        }
        
        if (start) {
            res.push_back(x>>k&1);
        }
    }

    return res;
}

vector<bool> next_seq(vector<bool>&a) {
    vector<bool> res;

    int j = 0;
    for (int i = 0; i < size(a);) {
        while (j < size(a) && a[j] == a[i]) {
            j++;
        }

        vector<bool> part = bin(j-i);
        res.insert(res.end(), part.begin(), part.end());
        res.push_back(a[i]);

        i = j;
    }

    return res;
}

const int MAXM = 1e6;

void solve(){
    vector<vector<bool>> seqs = {{1}, {1, 1}};

    while (size(end(seqs)[-2]) < MAXM) {
        seqs.push_back(next_seq(seqs.back()));
    }

    // int bad = 0;
    // for (int i = 2; i < size(seqs); i++) {
    //     for (int j = 0; j < size(seqs[i-2]); j++) {
    //         if (end(seqs[i-2])[-j-1] != end(seqs[i])[-j-1]) {
    //             bad++;
    //             cout << i << ' ' << j << '\n';
    //         }
    //     }
    // }
    // cout << bad << '\n';

    bool parity_last = size(seqs) % 2;

    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        m++;

        cout << end(seqs[size(seqs)-1 - (parity_last != (n&1))])[-m] << '\n';
    }
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
}