#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

void solve();
void init();

signed main() {
    fast
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

string s[2];
vector<int> lens = {0, 1};

string to_str(int x){
    string s;
    while(x){
        s.push_back('0' + (x & 1));
        x /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}

void init(){
    s[0] = "1";
    const int sz = 1e6 + 1;
    for(bool u = false, v = true; s[0].size() <= sz || s[1].size() <= sz; swap(u, v)){
        string &su = s[u], &sv = s[v];
        sv.clear();
        su.push_back('#');
        int len = 1; char lst = su[0];
        for(int i = 1; i < su.size(); i++){
            if(su[i] != lst){
                sv += to_str(len);
                sv += lst;
                len = 1, lst = su[i];
            }
            else{
                len++;
            }
        }
        su.pop_back();
        lens.push_back(sv.size());
//        cout << sv << '\n';
    }
}

void solve() {
    int n, m; cin >> n >> m;
    if(n < lens.size() && lens[n] <= m){
        cout << 0 << '\n';
    }
    else{
        string &t = s[!(n & 1)];
        cout << t[t.size() - m - 1] << '\n';
    }
}