#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int B=36;
int t;
ll n,m;
int len[40];
char s[40][1100005];
char qwq[10000005];
void trans(int x){
	int tot=0;
	for (int i=len[x];i>=1;i--){
		int j=i;
		while(j>1&&s[x][j-1]==s[x][i])j--;
		int l=i-j+1;
		qwq[++tot]=s[x][i];
		while(l>0)qwq[++tot]='0'+(l&1),l>>=1;
		i=j;
	}
	len[x+1]=min(tot,1100000);
	for (int i=1;i<=len[x+1];i++)s[x+1][i]=qwq[len[x+1]-i+1];
	return;
}
int main(){
	len[1]=1;
	s[1][1]='1';
	for (int i=1;i<=B;i++){
		trans(i);
	}
	cin>>t;
	while(t--){
		scanf("%lld%lld",&n,&m);
		if (n>B){
			if (n&1)n=B+1;
			else n=B;
		}
		if (m>=len[n])putchar('0');
		else putchar(s[n][len[n]-m]);
		putchar('\n');
	}
	return 0;
}