#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int t;
ll n,m;
vector<string> re;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s="1";
	int ms=2e6;
	for (int z=0;z<1000;++z)
	{
		string no;
		int cn=1;
		char cu='1';
		for (int i=1;i<(int)s.size();++i)
		{
			if (s[i]!=s[i-1])
			{
				for (int j=__lg(cn);j>=0;--j) no.pb('0'+((cn>>j)&1));
				no.pb(cu);
				cn=1;
				cu=s[i];
			}
			else ++cn;
		}
		for (int j=__lg(cn);j>=0;--j) no.pb('0'+((cn>>j)&1));
		no.pb(cu);
		if ((int)no.size()>ms) no=no.substr(no.size()-ms);
		s=no;
		re.pb(s);
		if (z>40)
		{
			if (re[z].substr(ms/2)==re[z-2].substr(ms/2)) break;
		}
	}
	re.insert(re.begin(),"1");
	cin>>t;
	while (t--)
	{
		cin>>n>>m;
		--n;
		if (n>=re.size())
		{
			n-=(n-re.size()+2)/2*2;
		}
		if (re[n].size()<=m) cout<<0<<en;
		else cout<<re[n][re[n].size()-m-1]<<en;
	}
}