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
#include<iostream>
#include<stdlib.h>
#include<stdint.h>
#include<vector>
#include<string>
#include<bitset>
#include<stdio.h>

using namespace std;

#define DEBUG
#define ASSERT

#ifdef DEBUG
#define ifdebug if(true)
#else
#define ifdebug if(false)
#endif

#ifdef ASSERT
#define ifassert if(true)
#else
#define ifassert if(false)
#endif


/* Wyniki
rysiek@Wc:~/Dropbox/potyczki2016/pok$ g++ tst.cpp && ./a.out
Graph size 1 has 1 versions; minimal K-s: k0=1
Graph size 2 has 2 versions; minimal K-s: k0=1 k1=1
Graph size 3 has 8 versions; minimal K-s: k0=1 k1=6 k2=1
Graph size 4 has 64 versions; minimal K-s: k0=1 k1=22 k2=40 k3=1
Graph size 5 has 1024 versions; minimal K-s: k0=1 k1=65 k2=570 k3=387 k4=1
Graph size 6 has 32768 versions; minimal K-s: k0=1 k1=171 k2=4970 k3=21837 k4=5788 k5=1
Graph size 7 has 2097152 versions; minimal K-s: k0=1 k1=420 k2=33887 k3=576247 k4=1353096 k5=133500 k6=1

Graph size = 2^( (n*(n-1)/2) )	// czyli potęga 2 (jest krawędź lub jej nie ma), do potęgi możliwych krawędzi dla danego punktu, a więc n-1 + n-2 + n-3 ... + 0 = n*(n-1)/2
*/


/// Silnia
int64_t factorial(int n) {
	int64_t res=1;
	for(int i=2;i<=n;++i) res*=i;
	return res;
}

/// Dwumian Newtona
int64_t newton(int n, int k) {
	int64_t res=1;
	for(int i=1;i<=k;++i) {
		res=res*(n-i+1)/i;
	}
	return res;
    //return factorial(n)/(factorial(k)*factorial(n-k));
}


int64_t calcK1(int n) {
	int it=n-1;
	int64_t res=0;
	int64_t m=newton(n, 1);
	for(int j=it;j>=2;--j) {
		res+=newton(it, j)*m;
	}
	res+=newton(n,2);
	return res;
}

int main(int argc, char** argv) {
	std::ios::sync_with_stdio(false);
	int q;

	cin>>q;
	for(int i=0;i<q;++i) {
		int n,k;
		cin>>n>>k;
		if(k==0 || k==n-1) cout<<"1"<<endl;
		else if(k==1) cout<<(calcK1(n)&1)<<endl;
		else cout<<"1"<<endl;	// nie mam pojęcia
	}

	return 0;
}