#include <bits/stdc++.h>
using namespace std;
#define int long long
string tobin(int x){
	string s = "";
	while(x){
		if(x%2==0){
			s.push_back('0');
		}
		else{
			s.push_back('1');
		}
		x/=2;
	}
	reverse(s.begin(),s.end());
	return s;
}
string next(string s){
	int cnt = 1;
	string ans = "";
	for(int i = 1; i<=s.size(); i++){
		if(i==s.size() || s[i] != s[i-1]){
			ans+=tobin(cnt);
			ans.push_back(s[i-1]);
			cnt = 1;
		}
		else{
			cnt++;
		}
	}
	return ans;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	vector<string>ans(39);
	string cur = "1";
	ans[1] = cur;
	for(int i = 2; i<=38; i++){
		cur = next(cur);
		ans[i] = cur;
	}
	while(t--){
		int n,m;
		cin >> n >> m;
		if(n<=38){
			if(ans[n].size()<=m){
				cout << "0\n";
			}
			else{
				cout << ans[n][(int)ans[n].size()-1-m] << '\n';
			}
		}
		else{
			int i = n%2 + 36;
			cout << ans[i][ans[i].size()-1-m] << '\n';
		}
	}
	return 0;
}