#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define mp make_pair

using pi = pair<int, int>;
using str = string;


const ll inf = 1e18;
mt19937 rnd(234);

const int maxM = 1e6, SZ = 38;

map<pi, int> dict;
str s[SZ];

str to_binary(int x) {
    str s;
    int id = -1;
    for (int i = 31; i >= 0; i--) {
        if (x & (1 << i)) {
            id = i;
            break;
        }
    }
    for (int i = id; i >= 0; i--) {
        if (x & (1 << i)) {
            s += '1';
        } else {
            s += '0';
        }
    }
    reverse(s.begin(), s.end());
    return s;
}

void precalc() {
    s[0] = "1";
    for (int i = 1; i < SZ; i++) {
        for (int l = 0, r = 0; l < s[i - 1].size() && s[i].size() < maxM; l = r) {
            while (r < s[i - 1].size() && s[i - 1][l] == s[i - 1][r]) {
                r++;
            }
            s[i] += s[i - 1][l];
            s[i] += to_binary(r - l);
        }
    }
}

void solve() {
    ll n;
    int m;
    cin >> n >> m;
    n--;
    if (n < SZ) {
        if (m >= s[n].size()) {
            cout << "0\n";
        } else {
            cout << s[n][m] << "\n";
        }
        return;
    }
    cout << s[n % 2 + 36][m] << "\n";
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    precalc();
    int test = 1;
    cin >> test;
    while (test--) {
        solve();
    }
    return 0;
}