#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MAX_LEN = 1e6 + 1000;

string to_bin(ll x) {
	string out;
	while (x > 0) {
		out += (x % 2) + '0';
		x /= 2;
	}
	reverse(out.begin(), out.end());
	return out;
}

string gen_next(string x) {
	string next_str;
	ll idx = 0;
	while (idx < x.length()) {
		char cur_char = x[idx];
		ll len = 0;
		while (idx + len < x.length() && x[idx + len] == cur_char) len++;

		next_str += to_bin(len) + cur_char;
		idx += len;
	}

	return next_str;
}

signed main() {
	ll t;
	cin >> t;

	string odd = "1", even = "11";
	while (odd.length() < MAX_LEN || even.length() < MAX_LEN) {
		odd = gen_next(even);
		even = gen_next(odd);
	}
	reverse(odd.begin(), odd.end());
	reverse(even.begin(), even.end());

	while (t--) {
		ll n, m;
		cin >> n >> m;

		if (n & 1) {
			cout << odd[m] << endl;
		} else {
			cout << even[m] << endl;
		}
	}
}