#include<bits/stdc++.h>

#pragma GCC optimize ("Ofast")
using namespace std;

#define rep(i,a,b) for(ll i = a; i<b;i++)
#define rrep(i,a,b) for(ll i = b-1; i>=a;i--)
#define trav(x,a) for(auto &x: a)
#define all(v) v.begin(),v.end()
#define sz(v) ll(v.size())

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    map<ll,vl> mp;
    mp[0].push_back(1);
    mp[1].push_back(2);
    mp[2].push_back(9);
    mp[2].push_back(3);
    mp[3].push_back(4);
    mp[4].push_back(5);
    mp[5].push_back(6);
    mp[5].push_back(3);
    mp[6].push_back(6);
    mp[6].push_back(0);
    mp[7].push_back(8);
    mp[8].push_back(7);
    mp[8].push_back(0);
    mp[9].push_back(9);
    mp[9].push_back(0);

    map<ll,string> mps;
    mps[0] = "01";
    mps[1] = "0111";
    mps[2] = "01111";
    mps[3] = "001";
    mps[4] = "00111";
    mps[5] = "001111";
    mps[6] = "0011";
    mps[7] = "1";
    mps[8] = "11";
    mps[9] = "011";

    vector<vl> s(1,vl(1,7));
    rep(i,0,60){
        s.emplace_back();
        for(auto x: s[sz(s)-2]){
            for(auto y:mp[x]) s.back().push_back(y);
            if(sz(s.back())>5e5) break;
        }
    }

    vector<string> a(sz(s));
    rep(i,0,sz(s)){
        for(auto x: s[i]){
            a[i] += mps[x];
        }
    }
    // cout<<"LENGTH: "<<sz(a[sz(a)-3])<<endl;

    // rep(i,0,10){
    //     reverse(all(a[i]));
    //     cout<<a[i]<<endl;
    // }

    rep(j,0,sz(a.back())){
        rep(i,0,57){
            if(sz(a[i])>j){
                // cout<<a[i][j];
                assert(a[i+2][j] == a[i][j]);
            }
        }
        // cout<<endl;
    }

    ll t; cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        n--;
        if(n>=60){
            n = 58+(n%2);
        }
        if(sz(a[n])>m) cout<<a[n][m];
        else cout<<0;
        cout<<"\n";
    }
}