#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=38;

string str[maxn+50];

void prepare(){
	str[1]="1";
	for (int i=2;i<=maxn;i++){
		int sz=str[i-1].length();
		int l=0;
		int r=0;
		for (;l<sz;l=r){
			for (;r<sz && str[i-1][r]==str[i-1][l];) r++;
			int tmp=r-l;
			vector<int> digit;
			for (;tmp;tmp/=2) digit.push_back(tmp%2);
			reverse(digit.begin(),digit.end());
			for (auto x:digit) str[i].push_back('0'+x);
			str[i].push_back(str[i-1][l]);
		}
	}
//	for (int i=1;i<=10;i++) cout << str[i] << "\n";
//	for (int i=1;i<=maxn;i++) cout << str[i].length() << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	prepare();
	
	int TC=1;
	cin >> TC;
	for (;TC--;){
		long long n,m;
		cin >> n >> m;
		if (n>=maxn){
			if (n%2==1) n=maxn-1;
			else n=maxn;
		}
		if (str[n].length()<=m){
			cout << 0 << "\n";
			continue;
		}
		else{
			int pos=(int)str[n].length()-1-m;
			cout << str[n][pos] << "\n";
		}
	}
	return 0;
}