#include<bits/stdc++.h>
using namespace std;
int N=36;
string ans[40];
string count(char x,int len){
	string RE;
	RE+=" ";
	RE[RE.size()-1]=x;
	while(len){
		RE+=" ";
		RE[RE.size()-1]=len%2+'0';
		len/=2;
	}
	return RE;
}
int main(){
	string s="1";
	ans[1]=s;
	for(int i=1;i<=N;i++){
		s+=" ";
		string ss;int zz=0;
		for(int j=0;j+1<s.size();j++){
			if(s[j]!=s[j+1]){
				ss+=count(s[j],j-zz+1);
				zz=j+1;
			}
		}
		s=ss;
		ans[i+1]=ss;
	}
	int T;
	long long n,m;
	cin>>T;
	while(T--){
		scanf("%lld%lld",&n,&m);
		if(n<=36){
			if(ans[n].size()<=m)puts("0");
			else{
				putchar(ans[n][m]);
				putchar('\n');
			}
		}
		else{
			char xx1=ans[36][m],xx2=ans[37][m];
			if(xx1==xx2){
				putchar(xx1);
				putchar('\n');
			}
			else{
				if(n&1)putchar(xx2);
				else putchar(xx1);
				putchar('\n');
			}
		}
	}
}