#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
vector<string> arr;

void solve() {
	ll n, m; cin >> n >> m;
	for (int i = 0; i < size(arr); i++) {
		if (size(arr[i]) > m && (i + 1) % 2 == n % 2) {
			cout << arr[i][size(arr[i]) - m - 1] << "\n";
			return;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	arr.push_back("1");
	for (int i = 1;; i++) {
		string s;
		for (int j = 0, jj = 0; j < size(arr[i - 1]); j = jj) {
			while (jj < size(arr[i - 1]) && arr[i - 1][j] == arr[i - 1][jj])
				jj++;
			int x = jj - j;
			for (int k = 31 - __builtin_clz(x); k >= 0; k--)
				s.push_back('0' + ((x >> k) & 1));
			s.push_back(arr[i - 1][j]);
		}
		arr.push_back(s);
		if (size(arr[i - 1]) > N)
			break;
	}
	int t; cin >> t; while (t--) solve();
}