#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))

typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
#define log(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }

signed main() {
    atexit([](){cerr << "time: " << (db)clock()/CLOCKS_PER_SEC << "s\n";});
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    vector<string> s; s.pb("1");
    for(int i = 1; SZ(s[i - 1]) <= 1.5e6; i++) {
        s.pb("");
        for(int j = 0, k; j < SZ(s[i - 1]); j = k + 1) {
            k = j; while(k + 1 < SZ(s[i - 1]) && s[i - 1][k + 1] == s[i - 1][k]) k++;
            string num;
            for(int t = k - j + 1; t; t >>= 1) num += t % 2 + '0';
            reverse(num.begin(), num.end());
            s[i] += num + s[i - 1][j];
        }
        // cerr << SZ(s[i]) << '\n';
    }
    for(int i = 0; i < SZ(s); i++) reverse(s[i].begin(), s[i].end());
    cerr << s[5] << '\n';
    int _; cin >> _; for(int cas = 1; cas <= _; cas++) {
        ll n, m;
        cin >> n >> m;
        if(n > SZ(s)) {
            n = SZ(s) - (n % 2 != SZ(s) % 2);
        }
        if(m >= SZ(s[n - 1])) {
            cout << "0\n";
        } else {
            cout << s[n - 1][m] << '\n';
        }
    }
    return 0;
}