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

using i64 = long long;

string toBS(int x) {
    string ret;
    while(x > 0) {
        ret.push_back('0' + x % 2);
        x /= 2;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

string evolve(const string &s) {
    string ret;
    for(int i = 0, cnt = 0; i < s.size(); i ++) {
        cnt ++;
        if(i + 1 >= s.size() || s[i] != s[i + 1]) {
            ret += toBS(cnt);
            ret.push_back(s[i]);
            cnt = 0;
        }
    }
    return ret;
}

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

    vector<string> t;
    t.push_back("1");
    while(t.back().size() < 2000000) t.push_back(evolve(t.back()));

    int T;
    cin >> T;
    while(T --) {
        i64 n, m;
        cin >> n >> m;
        if(n > t.size()) {
            n -= ((n - t.size() + 1) | 1) ^ 1;
        }
        n --;
        if(t[n].size() <= m) cout << "0\n";
        else cout << t[n][t[n].size() - 1 - m] << "\n";
    }
}