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

string tobin(int n) {
	if (n == 0) return "0";
	string ans;
	while (n) {
		ans.push_back('0' + (n % 2));
		n /= 2;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

string process(string s) {
	char prv = '-';
	int cnt = 0;
	string ans;
	for (char c: s) {
		if (c != prv) {
			if (prv == '-') {
				prv = c; cnt = 1; continue;
			} else {
				ans += tobin(cnt);
				ans += prv;
				prv = c; cnt = 1;
			}
		} else {
			cnt++;
		}
	}
	ans += tobin(cnt);
	ans += prv;
	return ans;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	vector<string> rx;
	string s = "1";
	rx.push_back(s);
	for (int i = 1; i <= 36; i++) {
		s = process(s);
		rx.push_back(s);
	}

	int t; cin >> t;
	while (t--) {
		long long n; int m;
		cin >> n >> m; n--;
		if (n <= 36) {
			if (m >= rx[n].size()) cout << "0\n"; 
			else cout << rx[n][rx[n].size() - m - 1] << '\n';
		} else {
			n %= 2; n ^= 1; n += 35;
			cout << rx[n][rx[n].size() - m - 1] << '\n';
		}
	}
	
	return 0;
}