#include<bits/stdc++.h>
using namespace std;
string s[40],w[2];
int len[40];
void cla(string& ans,const string& a)
{
	//string ans;
	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;char ss[32];
			itoa(num,ss,2);tmp2=ss;
			ans+=tmp2+tmp;
			num=1,tmp=a[i];
		}
	}
	string tmp2;char ss[32];
	itoa(num,ss,2);tmp2=ss;
	ans+=tmp2+tmp;
}
int main()
{
	s[1]="1";
	for(int i=2;i<=37;i++)
	{
		cla(s[i],s[i-1]);
		len[i]=s[i].length();//cout<<<<endl;
	}
	w[0]=s[36];
	w[1]=s[37];
	reverse(w[0].begin(),w[0].end());
	reverse(w[14].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;
}

answer.code: In function ‘void cla(std::string&, const std::string&)’:
answer.code:15:25: error: ‘itoa’ was not declared in this scope
   15 |                         itoa(num,ss,2);tmp2=ss;
      |                         ^~~~
answer.code:21:9: error: ‘itoa’ was not declared in this scope
   21 |         itoa(num,ss,2);tmp2=ss;
      |         ^~~~
answer.code: In function ‘int main()’:
answer.code:36:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |         int t;scanf("%d",&t);
      |               ~~~~~^~~~~~~~~