#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int mn = 1e6;
vector<vector<bool>> vals;

void append(vector<bool> &x, int t) {
	vector<bool> cur;
	while (t) {
		cur.push_back(t&1);
		t/=2;
	}
	while (cur.size()) {
		x.push_back(cur.back());
		cur.pop_back();
	}
}

vector<bool> iter(const vector<bool> &val) {
	vector<bool> out;
	int cnt = 0;
	int prev = val[0];
	for (int i = 0; i <= val.size(); i++) {
		int cur = i < val.size() ? val[i] : -1;
		if (prev != cur) {
			append(out, cnt);
			out.push_back(prev);
			prev = cur;
			cnt = 1;
		}
		else {
			cnt++;
		}
	}
	return out;
}

void solve() {
	ll n, m; cin >> n >> m;
	
	if (n < vals.size()) {
		cout << (m < vals[n].size() ? vals[n][vals[n].size()-1-m] : 0) << endl;
	}
	else {
		ll cur = n-vals.size();
		if (cur%1 == 0) cur--;
		ll x = n-cur-2;

		cout << (vals[x][vals[x].size()-1-m]) << endl;
	}
}

int main() {
	int t; cin >> t;
	vector<bool> init;
	vals.push_back({});
	init = {1};

	int cnt = 0;
	while (init.size() < mn) {
		cnt++;
		vals.push_back(init);
		init = iter(init);
	}
	vals.push_back(init);
	init = iter(init);
	vals.push_back(init);
	init = iter(init);
	
	while (t--) solve();
}