#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <array>

using namespace std;
typedef long long ll;

vector<string> s;

string nxt(string prv){
    int cnt = 0;
    string result = "";
    for(int i = 0; i < prv.size(); ++i){
        ++cnt;
        if(i == (int)prv.size() - 1 || prv[i] != prv[i + 1]){
            string to_add = "";
            while(cnt > 0){
                to_add += '0' + (cnt % 2);
                cnt /= 2;
            }
            while(!to_add.empty()){
                result += to_add.back();
                to_add.pop_back();
            }
            result += prv[i];
            cnt = 0;
            continue;
        }
    }
    return result;
}

void init(){
    s.push_back("1");
    s.push_back("11");

    while(s[s.size() - 2].size() < (int)1e6){
        s.push_back(nxt(s.back()));
        // cout << s.back().size() << endl;
        // if(s.back().size() < 100){
            // cout << s.back() << endl;
        // }
    }
}

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

    init();

    int t;
    cin >> t;

    while(t--){
        ll n, m;
        cin >> n >> m;
        --n;
        ++m;

        if(n < s.size()){
            if(m > s[n].size()){
                cout << "0\n";
                continue;
            }
            cout << s[n][(int)s[n].size() - m] << "\n";
            continue;
        }

        n &= 1;
        if((n & 1) == ((s.size() - 1) & 1)){
            n = s.size() - 1;
        }
        else{
            n = s.size() - 2;
        }
        cout << s[n][(int)s[n].size() - m] << "\n";
    }
}