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

const int MAXS = 39;
string strs[MAXS];

string get_next(string& str){
	string temp;
	int am = 0;
	char prev = '1';
	for(int i = 0; i < str.size(); i++){
		if(str[i] == prev){
			am++;
		}else{
			string temp2;
			while(am > 0){
				if(am & 1){
					temp2.push_back('1');
				}else{
					temp2.push_back('0');
				}
				am /= 2;
			}
			reverse(temp2.begin(), temp2.end());
			temp += temp2;
			temp += prev;
			am = 1;
		}
		prev = str[i];
	}
	string temp2;
	while(am > 0){
		if(am & 1){
			temp2.push_back('1');
		}else{
			temp2.push_back('0');
		}
		am /= 2;
	}
	reverse(temp2.begin(), temp2.end());
	temp += temp2;
	temp += prev;
	return temp;
}

void solve() {
    long long n;
    int m;
    cin >> n >> m;
    n--;

    if (n < MAXS && m >= strs[n].length()) {
        cout << "0\n";
        return;
    }

    if (n % 2 == 0) {
        int len = strs[MAXS - 1].length();
        cout << strs[MAXS - 1][len - m - 1] << "\n";
    } else {
        int len = strs[MAXS - 2].length();
        cout << strs[MAXS - 2][len - m - 1] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    strs[0] = "1";
    for (int i = 1; i < MAXS; i++) {
        strs[i] = get_next(strs[i - 1]);
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}