1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N  = 1<<15;
int W = 14;//14;
int T[15][N];
vector <int> bazy_potegowe[15];
vector <int> odp[(N>>2)  + 5];
int liczby_jedynek[N] = {0};

vector <int> mnozenie(const vector <int> &a,const vector <int> &b){
	vector <int> c;
	for (unsigned int i = 0; i < a.size(); ++i){
		for (unsigned int j = 0; j < b.size(); ++j){
			c.push_back(a[i] + b[j]);	
		}
	}
	sort(c.begin(), c.end());
	vector <int> d;
	for (unsigned int i = 0; i < c.size(); ++i){
		int k = 1;
		while(i != c.size()-1 && c[i] == c[i+1]){
			++i;
			++k;
		}
		if (k&1)d.push_back(c[i]);
	}
	return d;
}

main (){
	ios::sync_with_stdio(0);
	T[0][0] = 1;
	for (int i = 0; i < W; ++i){
		for (int j = 0; j < (1<<i); ++j){
			T[i+1][2*j] += T[i][j];
			T[i+1][2*j] &= 1;
			T[i+1][j + (1 << i)] += T[i][j];
			T[i+1][j + (1 << i)] &= 1;
		}
	}
	for (int i = 0; i <= W; ++i){
		for (int j = 0; j < (1<<i); ++j){
			if(T[i][j]){
				bazy_potegowe[i].push_back(j);		
			}
		}
		bazy_potegowe[i].push_back(1<<i);///trol den
	}
	for (int i = 0; i <= (N>>2); ++i){
		vector <int> x;
		x.push_back(0);
		for (int j = W; j >= 0; --j){
			if (i &(1<<j)){
				if (x.size() == 1){
					x = bazy_potegowe[j];
					x.pop_back();
				}
				else x = mnozenie(x, bazy_potegowe[j]);
			}
		}
		
		odp[i] = x;
	}
	int z;
	cin >> z;
	int n = 0;
	int k = 0;
	for (int i = 0; i < z; ++i){	
		cin >> n >> k;
		if (n <= (1<<13)){
			if (binary_search(odp[n].begin(), odp[n].end(), k))cout <<"1\n";
			else cout <<"0\n";
		}
		else if(n == (1 << 14)){
			if (binary_search(bazy_potegowe[14].begin(), bazy_potegowe[14].end(), k))cout <<"1\n";
			else cout <<"0\n";
		}
		else {
			int x = 0;
			for (int j = 0; j < 8; ++j){
				if (binary_search(odp[n - (1<<13)].begin(), odp[n-(1<<13)].end(), k - bazy_potegowe[13][j])) ++x;
			}
			if(x&1){
				cout <<"1\n";
			}
			else cout <<"0\n";
		}
	}
	return 0;
}