#include <bits/stdc++.h>
int main() {
    std::vector <std::string> Ans(1);
    Ans.push_back("1");
    long long n, m = 1e6;
    while (Ans[Ans.size() - 2].size() < m) {
        std::string t;
        std::string &s = Ans.back();
        for (int l = 0, r = 0; r < s.size(); l = r) {
            while (r < s.size() && s[l] == s[r]) ++r;
            for (int i = std::__lg(r - l); i >= 0; --i)
                t += '0' + (r - l >> i & 1);
            t += s[l];
        }
        Ans.push_back(t);
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        if (n > Ans.size()) 
            n = Ans.size() - (n - Ans.size() - 1) % 2 - 1;
        if (m < Ans[n].size())
            printf("%c\n", (char)Ans[n][Ans[n].size() - m - 1]);
        else puts("0");
    }
}