#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

const int L = 1234567;

string binary(int n) {
    string binStr = "";
    while (n > 0) {
        binStr = char((n % 2) + '0') + binStr;
        n /= 2;
    }
    return binStr;
}

string say(string A) {
    char c = '1';
    int cnt = 0;
    int mx_cnt = 0;
    string ans = "";
    for (char a : A) {
        if (a != c) {
            ans += binary(cnt) + c;
            c = a;
            cnt = 0;
        }
        cnt++;
    }
    ans += binary(cnt) + c;
    if (ans.length() > L) {
        ans = ans.substr(ans.length() - L);
    }
    return ans;
}

int main() {
    vector<string> s;
    s.push_back("1");
    for (int i = 0; i < 50; ++i) {
        s.push_back(say(s.back()));
    }

    int t;
    cin >> t;
    while(t--) cout << [&]() -> char {
        ll N, M;
        cin >> N >> M;
        N--;
        if (N > 50) {
            N -= (N - 48) / 2 * 2;
        }
        if (M >= s[N].length()) {
            return '0';
        } else {
            return s[N].rbegin()[M];
        }
    }() << '\n';
}