/*
60 + 0 + 100 + 64 = 224.
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define pb push_back
#define pii pair<int, int>
inline int read()
{
	int sum = 0, nega = 1;
	char ch = getchar();
	while (ch > '9'||ch < '0')
	{
	    if (ch == '-') nega = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * nega;
}
const int N = 2e6 + 9, mod = 998244353, Lim = 1e6;
inline void add(int &x, int y) {x = (x + y) % mod;}
inline void del(int &x, int y) {x = (x - y + mod) % mod;}
bitset<N * 2> B[59];
int len[59], t;
inline void init()
{
	L(i, 1, 1000)
	{
		if(i >= t && t) break;
		if(len[i] > Lim && !t) t = i + 1;
		int nw = 1;
		L(j, 1, len[i])
		{
			if(B[i][j] != B[i][j - 1] || j == len[i])
			{
				B[i + 1][len[i + 1]++] = B[i][j - 1];
				while(nw) B[i + 1][len[i + 1]++] = (nw & 1), nw /= 2;
				nw = 1;
			}
			else nw++;
		}
	//	if(i <= 19)
	//	{
	//		L(j, 0, 10) cout << B[i][j]; cout << endl;
	//	}
	}
	return ;
}
signed main()
{
	len[1] = 1, B[1][0] = 1; init();
	int Q = read();
	L(i, 1, Q)
	{
		int n = read(), m = read();
		if(n >= t)
		{
			if(n % 2 == t % 2) n = t;
			else n = t - 1;
			printf("%d\n", (int)B[n][m]);
		}
		else printf("%d\n", (int)B[n][m]);
	}
	return 0;
}