#include<bits/stdc++.h>
using namespace std;
string s[40],w[2];
int len[40];
string trans(int x)
{
	string ans;
	while(x)
	{
		if(x&1) ans="1"+ans;
		else ans="0"+ans;
		x=x/2;
	}
	return ans;
}
void cla(string& ans,const string& a)
{
	char tmp=a[0];int num=1;;
	for(int i=1;i<a.length();i++)
	{
		if(a[i]==a[i-1]) num++;
		else 
		{
			string tmp2=trans(num);
			ans+=tmp2+tmp;
			num=1,tmp=a[i];
		}
	}
	string tmp2=trans(num);
	ans+=tmp2+tmp;
}
int main()
{
	//cout<<trans(2)<<endl;
	s[1]="1";
	for(int i=2;i<=37;i++)
	{
		cla(s[i],s[i-1]);
		len[i]=s[i].length();
		//cout<<s[i]<<endl;
	}
	w[0]=s[36];
	w[1]=s[37];
	reverse(w[0].begin(),w[0].end());
	reverse(w[1].begin(),w[1].end());
	int t;scanf("%d",&t);
	while(t--)
	{
		long long n,m;cin>>n>>m;
		if(n<=37)
		{
			if(m>=len[n]) 
			{
				printf("0\n");
				continue;
			}
		} 
		cout<<w[n%2][m]<<endl;
	}
	return 0;
}