#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    auto binary = [&](int n) -> string {
        string res;
        while (n) {
            res += (char)('0' + n%2);
            n /= 2;
        }
        reverse(res.begin(), res.end());
        return res;
    };
    vector<string> str(38);
    str[0] = "1";
    for (int i = 1; i < 38; ++i) {
        for (int j = 0; j < str[i-1].size();) {
            int cnt = 0;
            char c = str[i-1][j];
            while (j < str[i-1].size() and str[i-1][j] == c) {
                cnt += 1; j += 1;
            }
            str[i] += binary(cnt);
            str[i] += c;
        }
    }
    int q; cin >> q;
    while (q--) {
        ll n,m; cin >> n >> m;
        if (n > 38) {
            if (n%2) n = 37;
            else n = 38;
        }
        n--; m += 1;
        if (str[n].size() < m) {
            cout << 0 << "\n";
        }
        else {
            cout << str[n][str[n].size()-m] << "\n";
        }
    }
}