0 1
1 10
2 0
3 1100
4 1
5 111000
6 0
7 11110000
8 111
9 1111100000
10 1
11 111111000000
12 11000
13 11111110001000
14 1
15 1111111100000000
16 1100000
17 111111111000001111
18 0
19 11111111110000100111
20 110000000
21 1111111111100010000011
22 0
23 111111111111000000000001
24 11000000000
25 11111111111110000000000000
26 0
27 1111111111111100001111000011
28 1100000000000
29 111111111111111000100110000001
30 0
31 11111111111111110000000000000000
32 110000000000000
33 1111111111111111100000100000000011
34 0
35 111111111111111111000010000000000001
36 11000000000000000
37 11111111111111111110001000000000000000
38 0
39 1111111111111111111100000000000000000000
40 1100001100000000011
41 111111111111111111111000000000000000000000
42 1
43 11111111111111111111110000111111000000000000
44 110000000000000000000
45 1111111111111111111111100010011100000000000000
46 100000000000011
47 111111111111111111111111000000000000000000000000
48 11000000000000000000001
49 11111111111111111111111110000011100110000000000000
50 0
51 1111111111111111111111111100001000000000000000000000
52 1100000111110000000000011
53 111111111111111111111111111000100000000000000000000000
54 11000000000000001
55 11111111111111111111111111110000000000001000000000000000
56 110000000000000000000000000
57 1111111111111111111111111111100000000000000000000000000000
58 100000000000000011
59 111111111111111111111111111111000011110000000000000000000000
60 11000000000000000000000000001
61 11111111111111111111111111111110001001000000000000000000000000
62 10000000000000000000000
63 1111111111111111111111111111111100000000000000000000000000000000
64 1100000000000000000000000000011
65 111111111111111111111111111111111000001111000000000000000000000000
66 10000000000000000000001
67 11111111111111111111111111111111110000100000000000000000000000000000
68 110000010000000000000000000000000
69 1111111111111111111111111111111111100010000000110000000000000000000000
70 11
71 111111111111111111111111111111111111000000000000000000000000000000000000
72 11000000001000000000000000000000001
73 11111111111111111111111111111111111110000000000001000000000000000000000000
74 0
75 1111111111111111111111111111111111111100001111100000000000000000000000000000
76 1100000000000000000000000000000000011
77 111111111111111111111111111111111111111000100100000000000000000000000000000000
78 1
79 11111111111111111111111111111111111111110000000000100000000000100000000000000000
80 110000000100000000000000000000000000000
81 1111111111111111111111111111111111111111100000111100000000000000000000000000000000
82 11
83 111111111111111111111111111111111111111111000010000000000000000000100000000000000000
84 11000001110000000000000000000000000000001
85 11111111111111111111111111111111111111111110001000000000000000000000000000000000000000
86 0
87 1111111111111111111111111111111111111111111100000000000110000000000000100000000000000000
88 1100000000000000000000000000000000000000011
89 111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000
90 110000000000000000000000000000001
91 11111111111111111111111111111111111111111111110000111110000000000000000000000000000000000000
92 110000000000000000000000000000000000000000000
93 1111111111111111111111111111111111111111111111100010010000000110000000000000000000000000000000
94 11
95 111111111111111111111111111111111111111111111111000000000010000000000000000000000000000000000000
96 11000000010000000000000000000000000000000000001
97 11111111111111111111111111111111111111111111111110000011110000000000000000000000000000000000000000
98 0
99 1111111111111111111111111111111111111111111111111100001000000000000000000000000000000000000000000000
100 1100000111110000000000000000000000000000000000011
101 111111111111111111111111111111111111111111111111111000100000000000000000000000000000000000000000000000
102 1
103 11111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000
104 110000000001100000000000000000000000000000000000000
105 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
106 11
107 111111111111111111111111111111111111111111111111111111000011111000000000000000000000000000000000000000000000
108 11000000000000000000000000000000000000000000000000001
109 11111111111111111111111111111111111111111111111111111110001001000000011100000000000000000000000000000000000000
110 11000000000000000000000000000000000000000000000
111 1111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000
112 1100000000000010000000000000000000000000000000000000011
113 111111111111111111111111111111111111111111111111111111111000001111111000000000000000000000000000000000000000000000
114 1
115 11111111111111111111111111111111111111111111111111111111110000100000000000000000000010000000000000000000000000000000
116 110000011111000000000000000000000000000000000000000000000
117 1111111111111111111111111111111111111111111111111111111111100010000000000000000000000000000000000000000000000000000000
118 11
119 111111111111111111111111111111111111111111111111111111111111000000000001111000000000000000000000000000000000000000000000
120 11000000000000000000000000000000000000000000000000000000001
121 11111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000
122 1111000000000000000000000000000000000000000000000
123 1111111111111111111111111111111111111111111111111111111111111100001111100000000000000000000000000000000000000000000000000000
124 1100000000000010000000000000000000000000000000000000000000011
125 111111111111111111111111111111111111111111111111111111111111111000100100000001010000000000000000000000000000000000000000000000
126 10000000000000000000000000000000000000000000001