#include <bits/stdc++.h>

using i64 = long long;
std::vector<std::string > res = {"0", "1", "11"};
int o = 2;

std::string binary(int n) {
    std::string s;
    while(n) {
        s += (n % 2) + '0';
        n /= 2;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

void get_string(std::string &s) {
    int n = s.size();
    std::string t;
    for (int i = 0; i < n; i += 1) {
        int j = i;
        int c = 0;
        while(j < n && s[j] == s[i]) {
            j += 1;
            c += 1;
        }
        t += binary(c) + s[i];
        i = j - 1;
    }
    res.push_back(t);
};

void solve(){
    while(res[o].size() < 1000000 || res[o - 1].size() < 1000000) {
        get_string(res[o]);
        o += 1;
    }
    i64 n;
    int m;
    std::cin >> n >> m;
    if (n >= 37) {
        if (n % 2) n = 37;
        else n = 36;
    }
    if (m >= res[n].size()) {
        std::cout << 0 << "\n";
    }
    else {
        std::cout << res[n][int(res[n].size()) - 1 - m] << "\n";
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}