Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are $N$ heaps of candies (numbered $1$ through $N$); for each valid $i$, the $i$-th of them contains exactly $i^{K}$ candies. You aim to partition these heaps between you and your friend in such a way that each heap is given to exactly one of you without being split among you.

The distribution should be as fair as possible. Formally, let's denote the total number of candies you get by $A$ and the total number of candies your friend gets by $B$; your goal is to minimise $|A-B|$.

Find the smallest possible value of $|A-B|$ and assign the heaps to you and your friend in some way that minimises $|A-B|$. If there are multiple solutions, you may find any one of them.

------  Input ------
The first line of the input contains a single integer $K$, which is common for all test cases.
The second line contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------  Output ------
For each test case, print two lines.
The first of these lines should contain a single integer ― the smallest value of $|A-B|$ we can obtain.
The second line should contain $N$ characters describing your assignment of heaps. For each valid $i$, the $i$-th of them should be '1' if you want to give the $i$-th heap to you or '0' if you want to give it to your friend.

------  Constraints  ------
$1 ≤ T ≤ 2,000$
$1 ≤ K ≤ 4$
$1 ≤ N ≤ 10^{6}$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (5 points): $K = 1$

Subtask #2 (10 points): $K = 2$

Subtask #3 (15 points): $K = 3$

Subtask #4 (70 points): $K = 4$

------  Example Input 1 ------

2
2
4
5

------  Example Output 1 ------

2
0001
3
01001

------  Explanation ------
Example case 1: There are four heaps with sizes $1$, $4$, $9$ and $16$ and two optimal assignments: either give the last heap to yourself and the rest to your friend or vice versa (so both "0001" and "1110" would be considered correct outputs). In both cases, $|A-B| = |16 - (1 + 4 + 9)| = 2$.

Example case 2: There are five heaps with sizes $1$, $4$, $9$, $16$ and $25$. You can assign the second and fifth heap to yourself, and thus $|A-B| = |(25 + 4) - (16 + 9 + 1)| = 3$. It can be proved that this is the smallest possible value of $|A-B|$.

------  Example Input 2 ------

4
3
5
6
9

------  Example Output 2 ------

271
00001
317
000001
253
000001110

------  Explanation ------
Example case 3: We have $K = 4$ and $N = 9$. The smallest value of $|A-B|$ is $|(6^{4} + 7^{4} + 8^{4}) - (1^{4} + 2^{4} + 3^{4} + 4^{4} + 5^{4} + 9^{4})| = |7793 - 7540|= 253$.

Difficulty: VERY_HARD
Tags: Bit manipulation

Combinatorics

Dynamic programming

Mathematics

Matrices
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
k = int(input())
if k == 2:
	for _ in range(int(input())):
		n = int(input())
		d = dict()
		s = ''
		d[1] = '1'
		d[2] = '01'
		d[3] = '001'
		d[4] = '0001'
		d[8] = '01101001'
		d[9] = '100111010'
		d[10] = '0111000101'
		d[11] = '01000111010'
		d[5] = '01001'
		d[6] = '001001'
		d[7] = '0010110'
		d[12] = '000000001101'
		d[13] = '0101010100101'
		d[14] = '10110100100011'
		while n >= 14:
			s += '01101001'
			n -= 8
		s = d[n] + s
		if n == 1:
			print(1)
		elif n == 2:
			print(3)
		elif n == 4:
			print(2)
		elif n == 5:
			print(3)
		elif n == 3:
			print(4)
		elif n % 4 == 1 or n % 4 == 2:
			print(1)
		else:
			print(0)
		print(s)
elif k == 1:
	for _ in range(int(input())):
		n = int(input())
		ans = ['0'] * (n + 1)
		s = 0
		su = n * (n + 1) // 2
		t = n * (n + 1) // 4
		if n == 2:
			ans = ['0', '1']
		else:
			for i in range(n, -1, -1):
				s += i
				ans[i] = '1'
				if t - s == 1:
					ans[1] = '1'
					break
				elif t - s < i and ans[t - s] == '0':
					ans[t - s] = '1'
					break
			ans = ans[1:]
		if su % 2 == 0:
			print(0)
		else:
			print(1)
		print(''.join(ans))
elif k == 3:
	for _ in range(int(input())):
		n = int(input())
		d = dict()
		d[1] = '1'
		d[2] = '01'
		d[3] = '001'
		d[4] = '0001'
		d[5] = '00001'
		d[6] = '011110'
		d[7] = '0001110'
		d[11] = '00001101001'
		d[12] = '001011100110'
		d[13] = '0000111011010'
		d[14] = '01011001101001'
		d[15] = '001111010111100'
		d[16] = '0110100110010110'
		d[17] = '10010110111110010'
		d[18] = '010011010101011010'
		d[8] = '00110110'
		d[9] = '011010110'
		d[10] = '1111111010'
		d[19] = '1100110110100111100'
		d[20] = '01011111110111111000'
		d[21] = '001010011111111010010'
		d[22] = '0001000111111101111000'
		d[23] = '10001111101111110111000'
		d[24] = '101011110110111110111000'
		d[25] = '0001111011111111111110000'
		d[26] = '01111111001101111111101000'
		d[27] = '011101101111111011111110000'
		s = ''
		while n >= 28:
			n -= 16
			s += '0110100110010110'
		s = d[n] + s
		if n == 1:
			print(1)
		elif n == 2:
			print(7)
		elif n == 3:
			print(18)
		elif n == 8:
			print(4)
		elif n == 9:
			print(5)
		elif n == 4:
			print(28)
		elif n == 5:
			print(25)
		elif n == 6:
			print(7)
		elif n == 7:
			print(26)
		elif n == 10:
			print(1)
		elif n == 11:
			print(12)
		elif n % 4 == 1 or n % 4 == 2:
			print(1)
		else:
			print(0)
		print(s)
else:
	for _ in range(int(input())):
		n = int(input())
		d = dict()
		d[1] = '1'
		d[2] = '01'
		d[3] = '001'
		d[4] = '0001'
		d[5] = '00001'
		d[6] = '000001'
		d[7] = '0000001'
		d[8] = '00101110'
		d[9] = '000001110'
		d[10] = '0101001001'
		d[11] = '00000101001'
		d[12] = '001101010110'
		d[13] = '0010110101001'
		d[20] = '00001010110111011100'
		d[21] = '000000000100100100011'
		d[22] = '1101001111011111110100'
		d[23] = '00001000100110111101100'
		d[24] = '000010011110110111110100'
		d[25] = '0101110101111110111111000'
		d[26] = '00010100000100010000110101'
		d[14] = '00000001111010'
		d[15] = '011110001010110'
		d[16] = '0000111000001110'
		d[17] = '00101000011111100'
		d[18] = '000000110100001110'
		d[19] = '1000010010110111100'
		d[27] = '001111000000011110111111000'
		d[28] = '0001011111000101111011111000'
		d[29] = '01010100010001011111010101010'
		d[30] = '010110010011011011111111011000'
		d[31] = '1111111111110100000010000101011'
		d[32] = '01101001100101101001011001101001'
		d[50] = '11111111111111111111111111111111101101010011100100'
		d[51] = '111111111111111111110001010111000111010101010101001'
		d[52] = '1111111111111111111101010000001000010101011001000111'
		d[53] = '11111111111111111111111111111110001101011010100101001'
		d[54] = '111111111111111111111101000110000001001101010101010101'
		d[55] = '1111111111111111111111010100110101110100110101010101010'
		d[56] = '00000001000001000011110111111111011111111111111110000000'
		d[57] = '010001011101010111010111110111111111011111111111110000000'
		d[58] = '0010111101100111110111111111111111111111111011111110000000'
		d[59] = '00000101000100010111010111111111111111111111101111110000000'
		d[60] = '000100010101010000110101111111111111111111111111011110000000'
		d[61] = '1110100011011010101010110010111100111110011011111011011010000'
		d[33] = '111111111101110101000011110101010'
		d[34] = '1111101111111011111010101111100010'
		d[35] = '11111111110101010011110100101101010'
		d[36] = '111111111111011110000100000101000111'
		d[37] = '1111111110101111111111101001101000101'
		d[38] = '11111111111111010001100001010110010101'
		d[39] = '111111111111111001010100010111010100110'
		d[40] = '1111111111111101010110100001000101000111'
		d[41] = '11111111111111110001010101100100010111010'
		d[45] = '111111111111111111101011011111111001101100100'
		d[46] = '1111111111111111110001100000010000010111010101'
		d[47] = '11111111111111111101010100100001000101010110110'
		d[48] = '111111111111111111011101000100010101100110010101'
		d[49] = '1111111111111111111101010101000001110100010111010'
		d[42] = '111111111111111111101101111111111001101000'
		d[43] = '1111111111111111010000010000000001111001110'
		d[44] = '11111111111111111000001001010001010011010101'
		s = ''
		while n >= 62:
			n -= 32
			s += '01101001100101101001011001101001'
		s = d[n] + s
		if n == 1:
			print(1)
		elif n == 2:
			print(15)
		elif n == 3:
			print(64)
		elif n == 4:
			print(158)
		elif n == 10:
			print(13)
		elif n == 11:
			print(92)
		elif n == 12:
			print(30)
		elif n == 13:
			print(47)
		elif n == 5:
			print(271)
		elif n == 6:
			print(317)
		elif n == 7:
			print(126)
		elif n == 8:
			print(34)
		elif n == 9:
			print(253)
		elif n == 14:
			print(31)
		elif n == 15:
			print(2)
		elif n == 16:
			print(0)
		elif n == 17:
			print(1)
		elif n == 23:
			print(0)
		elif n == 24:
			print(0)
		elif n == 25:
			print(1)
		elif n == 26:
			print(5)
		elif n == 27:
			print(0)
		elif n == 28:
			print(0)
		elif n == 18:
			print(13)
		elif n == 19:
			print(0)
		elif n == 20:
			print(0)
		elif n == 21:
			print(9)
		elif n == 22:
			print(1)
		elif n == 29:
			print(5)
		elif n % 4 == 1 or n % 4 == 2:
			print(1)
		else:
			print(0)
		print(s)


def reverse(string):
	string = ''.join(reversed(string))
	return string

def findTwoGroup(n):
	for i in range(3):
		sdf = 34
	cc1 = 0
	cc2 = 0
	res = ''
	sum = n * (n + 1) / 2
	group1Sum = sum / 2
	i = n
	while i > 0:
		if group1Sum - i >= 0:
			res = res + '0'
			group1Sum = group1Sum - i
			cc1 = cc1 + i
		else:
			res = res + '1'
			cc2 = cc2 + i
		i = i - 1
	res = reverse(res)
	print(abs(cc1 - cc2))
	print(res)

def findTwoGroup2(n):
	if n == 1:
		print(1)
		print(1)
		return
	if n == 2:
		print(3)
		print(10)
		return
	if n == 3:
		print(4)
		print(110)
		return
	if n == 4:
		print(2)
		print('0001')
		return
	if n == 5:
		print(3)
		print('01001')
		return
	if n == 6:
		print(1)
		print(101001)
		return
	res = ''
	count1 = 0
	count2 = 0
	i = n
	while i > 0:
		if count1 == count2:
			count1 = i * i
			count2 = 0
			res = res + '0'
			i = i - 1
			continue
		if count1 > count2:
			count2 = count2 + i * i
			res = res + '1'
			i = i - 1
			continue
		if count1 < count2:
			count1 = count1 + i * i
			res = res + '0'
			i = i - 1
			continue
	res = reverse(res)
	if abs(count1 - count2) == 4:
		print(0)
		temp = '10111000101'
		temp1 = res[len(temp):]
		res = temp
		res = res + temp1
		print(res)
		return
	if abs(count1 - count2) == 2:
		temp = '111111110010'
		temp1 = res[len(temp):]
		res = temp
		res = res + temp1
		print(0)
		print(res)
		return
	if abs(count1 - count2) == 3:
		if n % 8 == 2:
			temp = '0111000101'
			temp1 = res[len(temp):]
			res = temp
			res = res + temp1
			print(1)
			print(res)
		else:
			temp = '1110100010101'
			print(1)
			temp1 = res[len(temp):]
			res = temp
			res = res + temp1
			print(res)
		return
	print(abs(count1 - count2))
	print(res)
	return

def findTwoGroup3(n):
	for i in range(3):
		asfa = 34
	for i in range(3):
		sfda = 3
	answers = [0, 1, 7, 18, 28, 25, 7, 26, 4, 5, 1, 12, 0, 1, 1]
	aaa = ['', '1', '01', '001', '0001', '00001', '011110', '0001110', '00110110', '011010110', '1111111010', '00001101001', '110100011001', '0011110101001', '01011001101001']
	if n < 15:
		print(answers[n])
		print(aaa[n])
		return
	res = ''
	count1 = 0
	count2 = 0
	for i in range(4):
		asdfds = 4
	i = n
	while i > 0:
		if count1 == count2:
			count1 = i * i * i
			count2 = 0
			res = res + '0'
			i = i - 1
			continue
		if count1 > count2:
			count2 = count2 + i * i * i
			res = res + '1'
			i = i - 1
			continue
		if count1 < count2:
			count1 = count1 + i * i * i
			res = res + '0'
			i = i - 1
			continue
	res = reverse(res)
	for i in range(1):
		saf = 3
	map1 = {}
	map1[2] = '010011010101011010'
	map1[3] = '1100110110100111100'
	map1[4] = '11111110101010011001'
	map1[5] = '111011001011010010110'
	map1[6] = '1111111110010000111001'
	map1[7] = '11111111100101110011100'
	map1[8] = '111111111111010100001110'
	map1[9] = '1111111111101010010010101'
	map1[10] = '11111111101101101001110001'
	map1[11] = '111111111110110000001000111'
	map1[12] = '1111111111011011101101001001'
	map1[13] = '11111111110100000110110010110'
	if n % 16 >= 2 and n % 16 <= 13:
		ccc1 = n % 16
		rrr = map1[ccc1]
		temp = res[ccc1 + 16:]
		res = rrr
		res = res + temp
		if n % 4 == 0 or n % 4 == 3:
			print(0)
		else:
			print(1)
		print(res)
		return
	for i in range(4):
		asdf = 4
	print(abs(count1 - count2))
	print(res)
	for i in range(1):
		sfsdasfs = 1
	return
k = int(input())
wrong_ans = 0
for _ in range(int(input())):
	n = int(input())
	if k == 1:
		findTwoGroup(n)
	if k == 2:
		findTwoGroup2(n)
	if k == 3:
		findTwoGroup3(n)
	if k == 4:
		prelist = [0, 1, 15, 64, 158, 271, 317, 126, 34, 253, 13, 92, 30, 47, 31, 2, 0, 1, 13, 0, 0, 9, 1, 0, 0, 1, 5, 0, 0, 5, 1]
		prestring = ['', '1', '01', '001', '0001', '00001', '000001', '0000001', '00101110', '000001110', '0101001001', '00000101001', '001101010110', '0010110101001', '00000001111010', '011110001010110', '1111000111110001', '11111101001101001', '000000110100001110', '1110011000000110110', '11110101001000100011', '000000000100100100011', '1111011010010001111100', '11111100100111000100011', '111111011000000000011110', '1111111101010100001111100', '00010100000100010000110101', '111111010101001100110010110', '1111111101110011010000000111', '01010100010001011111010101010', '111111111101011100100001010011']
		if n < 31:
			print(prelist[n])
			print(prestring[n])
			continue
		else:
			cc1 = 0
			cc2 = 0
			res = ''
			for i in range(n):
				if cc1 == cc2:
					cc1 = 0
					cc2 = 0
					cc1 = cc1 + pow(n - i, 4)
					res = res + '0'
					continue
				if cc1 > cc2:
					cc2 = cc2 + pow(n - i, 4)
					res = res + '1'
					continue
				if cc1 < cc2:
					cc1 = cc1 + pow(n - i, 4)
					res = res + '0'
					continue
			res = reverse(res)
			dict = {2: '0111000101000101010101000101010101', 3: '11111111110101010011110100101101010', 4: '111111111111011110000100000101000111', 5: '0111000101010100000001010101010001011', 6: '11111111111111100100010100100011010101', 7: '111111111111111001010100010111010100110', 8: '1111111111111101010110100001000101000111', 9: '11111111111111111101000100011101000111010', 10: '111111111111111110111010111010101010110001', 11: '1111111111111111010000010000000001111001110', 12: '11111111111111111000001001010001010011010101', 13: '111111111111111111011010111010111110000010101', 14: '1111111111111111111100100100010101110001010101', 15: '11111111111111111101010100100001000101010110110', 16: '1111000111110001', 17: '', 18: '11111111111111111111111111111110100101100010001110', 20: '11110101001000100011', 21: '11111111111111111111111111111100011000101001101110100', 22: '1111011010010001111100', 23: '11111100100111000100011', 24: '111111011000000000011110', 25: '1111111101010100001111100', 26: '1111111111111111111111111111111111010111111111001100110000', 28: '1111111101110011010000000111', 29: '1111111111111111111111111111111111111101110111011011000000110'}
			if n % 32 >= 2 and n % 32 <= 18 or (n % 32 >= 20 and n % 32 <= 26) or (n % 32 >= 28 and n % 32 <= 29):
				if n == 17:
					print(1)
					print(res)
					continue
				c = n % 32
				tstring = str(dict[c])
				temp = res[len(tstring):]
				res = tstring
				res += temp
				temp_var = 0
				if n % 4 == 0 or n % 4 == 3:
					temp_var = 0
				else:
					temp_var = 1
				count1 = 0
				count2 = 0
				for ii in range(len(res)):
					if res[ii] == '0':
						count1 = count1 + pow(ii + 1, 4)
						continue
					else:
						count2 = count2 + pow(ii + 1, 4)
						continue
				tt = count1 - count2
				if tt < 0:
					tt = -1 * tt
				if tt != temp_var:
					print(n)
					print('ERROR')
					wrong_ans = wrong_ans + 1
					continue
				if n % 4 == 0 or n % 4 == 3:
					print(0)
					print(res)
					continue
				else:
					print(1)
					print(res)
					continue
			for i in range(4):
				sfda = 4
			print(abs(cc1 - cc2))
			print(res)
			temp_var = 0
			if n % 4 == 0 or n % 4 == 3:
				temp_var = 0
			else:
				temp_var = 1
			for i in range(1):
				sadf = 4
			count1 = 0
			count2 = 0
			for ii in range(len(res)):
				if res[ii] == '0':
					count1 = count1 + pow(ii + 1, 4)
					continue
				else:
					count2 = count2 + pow(ii + 1, 4)
					continue
			tt = count1 - count2
			if tt < 0:
				tt = -1 * tt
			if tt != temp_var:
				print(n)
				print('ERROR')
				wrong_ans = wrong_ans + 1
				continue
			continue


R = [[0], [9], [105], [27030], [2523490710]]
Big = [[0], [9, 18, 26, 52], [105, 326, 658, 1309, 2816, 6408, 12614, 28691], [27030, 90263, 92850, 399948, 918533, 1648646, 3702784, 7406094, 14813450, 29889024, 62915890, 125862033, 251695659, 503842239, 1010828723, 2017527202], [2523490710, 8053349460, 15578169898, 32229116701, 64558800214, 118113706624, 258775996118, 523987082687, 1065152269759, 2130370913629, 4260649664641, 8523362893015, 17059610646495, 34119230693507, 68444601276249, 138538467284949, 277076998389211, 554154935424477, 1108342088929856, 2216752889290741, 4434330462213117, 8901646138483052, 10584287182324789, 21168574364395247, 42337148729313391, 84674297460704590, 169348596241164840, 338697189842886595, 677394379686042647, 1354788753354093951, 2709577518758778734, 5419155037551137252]]
Small = [[0], [1, 1, 3], [0, 2, 4, 8, 18, 37, 75], [0, 2, 4, 8, 16, 34, 56, 108, 214, 641, 1200, 2443, 6176, 9626, 24899], [0, 2, 4, 8, 16, 32, 64, 116, 224, 586, 1184, 1708, 4788, 6016, 13598, 36751, 86046, 115392, 398046, 804015, 1610240, 3408949, 6563567, 13650031, 29377870, 45123624, 117579715, 235428887, 243845128, 956323694, 1946227172]]
k = int(input())

def D(num, l):
	s1 = 0
	s2 = 0
	for i in range(l):
		if num % 2 == 0:
			s1 += (i + 1) ** k
		else:
			s2 += (i + 1) ** k
		num = num // 2
	return abs(s1 - s2)

def cbin(num, l):
	s = bin(num)[2:][::-1]
	s = s + '0' * (l - len(s))
	return s
for _ in range(int(input())):
	n = int(input())
	if n < 2 ** (k + 1):
		print(D(Small[k][n - 1], n), '\n', cbin(Small[k][n - 1], n), sep='')
	else:
		if n % 4 == 1 or n % 4 == 2:
			print('1')
		else:
			print('0')
		if n % 2 ** (k + 1):
			print(cbin(Big[k][n % 2 ** (k + 1)], n % 2 ** (k + 1) + 2 ** (k + 1)), end='')
			n = n - 2 ** (k + 1) - n % 2 ** (k + 1)
		n = n // 2 ** (k + 1)
		for __ in range(n):
			print(cbin(R[k][0], 2 ** (k + 1)), end='')
		print()


k = int(input())
if k == 1:
	for _ in range(int(input())):
		n = int(input())
		if n == 1:
			print(1)
			print('1')
		if n == 2:
			print(1)
			print('01')
		if n == 3:
			print(0)
			print('001')
		if n == 4:
			print(0)
			print('1001')
		if n > 4:
			reqsum = n * (n + 1) // 4
			cursum = 0
			print(n * (n + 1) // 2 % 2)
			s = ['0' for i in range(n)]
			for i in range(n, 0, -1):
				if cursum + i <= reqsum:
					cursum += i
					s[i - 1] = '1'
			print(''.join(s))
if k == 2:
	base = 8
	ans = ['' for i in range(2 * base + 1)]
	ans[1] = '0'
	ans[2] = '10'
	ans[3] = '001'
	ans[4] = '0001'
	ans[5] = '01001'
	ans[6] = '010110'
	ans[7] = '1101001'
	ans[8] = '01101001'
	ans[9] = '100111010'
	ans[10] = '0100100101'
	ans[11] = '10111000101'
	ans[12] = '101000111010'
	ans[13] = '0000000110110'
	ans[14] = '00001100100011'
	ans[15] = '100000001001101'
	ans[16] = '1111011011000101'
	for _ in range(int(input())):
		n = int(input())
		store_diff = [-1, 1, 3, 4, 2, 3, 1, 0, 0]
		if n <= 2 * base:
			if n <= base:
				print(store_diff[n])
			else:
				print(int(n % 4 in [1, 2]))
			print(ans[n])
		if n > 2 * base:
			anss = ''
			anss += ans[(n - base) % base + base]
			for i in range((n - base) // base):
				anss += ans[base]
			print(int(n % 4 in [1, 2]))
			print(anss)
if k == 3:
	base = 16
	ans = ['' for i in range(2 * base + 1)]
	ans[1] = '1'
	ans[2] = '10'
	ans[3] = '110'
	ans[4] = '0001'
	ans[5] = '11110'
	ans[6] = '011110'
	ans[7] = '1110001'
	ans[8] = '11001001'
	ans[9] = '100101001'
	ans[10] = '0111111010'
	ans[11] = '00001101001'
	ans[12] = '110100011001'
	ans[13] = '0011110101001'
	ans[14] = '10100110010110'
	ans[15] = '001111010111100'
	ans[16] = '0110100110010110'
	ans[17] = '00110100110010110'
	ans[18] = '010011010101011010'
	ans[19] = '1001011011011000101'
	ans[20] = '11001100000000011110'
	ans[21] = '001010011111111010010'
	ans[22] = '0101001100011110101010'
	ans[23] = '00011100100000010111001'
	ans[24] = '100010110010001111000101'
	ans[25] = '0011100100011011111010010'
	ans[26] = '10110000110111000000110011'
	ans[27] = '011001001010111000110100101'
	ans[28] = '1001011000101000111010011001'
	ans[29] = '01011000100001000011001001011'
	ans[30] = '101100010101001101011111100100'
	ans[31] = '1000000000010001000001101001011'
	ans[32] = '01000000000000000011000010011011'
	for _ in range(int(input())):
		n = int(input())
		store_diff = [-1, 1, 7, 18, 28, 25, 7, 26, 4, 5, 1, 12, 0, 1, 1, 0, 0, 1]
		if n <= 2 * base:
			if n <= base:
				print(store_diff[n])
			else:
				print(int(n % 4 in [1, 2]))
			print(ans[n])
		if n > 2 * base:
			anss = ''
			anss += ans[(n - base) % base + base]
			for i in range((n - base) // base):
				anss += ans[base]
			print(int(n % 4 in [1, 2]))
			print(anss)
if k == 4:
	base = 32
	ans = ['' for i in range(2 * base + 1)]
	ans[1] = '1'
	ans[2] = '01'
	ans[3] = '110'
	ans[4] = '0001'
	ans[5] = '00001'
	ans[6] = '000001'
	ans[7] = '0000001'
	ans[8] = '00101110'
	ans[9] = '000001110'
	ans[10] = '0101001001'
	ans[11] = '00000101001'
	ans[12] = '001101010110'
	ans[13] = '1101001010110'
	ans[14] = '11111110000101'
	ans[15] = '011110001010110'
	ans[16] = '0000111000001110'
	ans[17] = '10000010110010110'
	ans[18] = '000000110100001110'
	ans[19] = '0111101101001000011'
	ans[20] = '11100100111001000011'
	ans[21] = '111111111011011011100'
	ans[22] = '0101001111011111110100'
	ans[23] = '10001100110001101011010'
	ans[24] = '010000110110110110011010'
	ans[25] = '1010001010000001000000111'
	ans[26] = '11101011111011101111001010'
	ans[27] = '100000100110100111110110010'
	ans[28] = '0000011000110011100110101001'
	ans[29] = '01000100000101011100011101010'
	ans[30] = '100010010001010111111111011000'
	ans[31] = '1101100001110111011111111101000'
	ans[32] = '10010110011010010110100110010110'
	ans[33] = '000000000010001010111100001010101'
	ans[34] = '0000010000000100000101010000011101'
	ans[35] = '01000111001011010111111101111110000'
	ans[36] = '100101010100011101111111111011110000'
	ans[37] = '1111111010111011111110111111111000100'
	ans[38] = '10010100100101011111110111111101110000'
	ans[39] = '000000100100010111110111111111111010000'
	ans[40] = '0000000000000010101001011110111010111000'
	ans[41] = '00000000000000000010111011100010111000101'
	ans[42] = '000000000000000000010010000000000110010111'
	ans[43] = '0000000000000000101111101111111110000110001'
	ans[44] = '00000000000000000111110110101110101100101010'
	ans[45] = '000000000000000000010100100000000110010011011'
	ans[46] = '0000000000000000000011011011101010001110101010'
	ans[47] = '00000000000000000010101011011110111010101001001'
	ans[48] = '000000000000000000100010111011101010011001101010'
	ans[49] = '0000000000000000000010101010111110001011101000101'
	ans[50] = '00000000000000000000000000000000010010101100011011'
	ans[51] = '000000000000000000001110101000111000101010101010110'
	ans[52] = '0000000000000000000010101111110111101010100110111000'
	ans[53] = '00000000000000000000000000000001110010100101011010110'
	ans[54] = '000000000000000000000001101111101010101011001010001110'
	ans[55] = '0000001101100011101110001101001100101101001011001101001'
	ans[56] = '00000010011111111110000101101001100101101001011001101001'
	ans[57] = '000000001010101111000001101101001100101101001011001101001'
	ans[58] = '0000000000000000000000000000000000000011001010011010110011'
	ans[59] = '00000010101011001100110100101101001100101101001011001101001'
	ans[60] = '000000001000110010111111100001101001100101101001011001101001'
	ans[61] = '0000000000000000000000000000000000000000101010111111011100001'
	ans[62] = '00000000001010001101111010110001101001100101101001011001101001'
	ans[63] = '000000000000101111110111101010001101001100101101001011001101001'
	ans[64] = '0110100110010110100101100110100101101001100101101001011001101001'
	for _ in range(int(input())):
		n = int(input())
		store_diff = [-1, 1, 15, 64, 158, 271, 317, 126, 34, 253, 13, 92, 30, 47, 31, 2, 0, 1, 13, 0, 0, 9, 1, 0, 0, 1, 5, 0, 0, 5, 1, 0, 0, 1, 1, 0, 0]
		if n <= 2 * base:
			if n <= base:
				print(store_diff[n])
			else:
				print(int(n % 4 in [1, 2]))
			print(ans[n])
		if n > 2 * base:
			anss = ''
			anss += ans[(n - base) % base + base]
			for i in range((n - base) // base):
				anss += ans[base]
			print(int(n % 4 in [1, 2]))
			print(anss)


try:
	k = int(input())
	for i in range(int(input())):
		n = int(input())
		if k == 1:
			mn = 0
			if n % 4 == 1 or n % 4 == 2:
				mn = 1
			s1 = '1'
			s2 = '01'
			s3 = '001'
			s4 = '1001'
			s = ''
			print(mn)
			if n == 1:
				print(s1)
			elif n == 2:
				print(s2)
			elif n == 3:
				print(s3)
			elif n == 4:
				print(s4)
			else:
				j = n
				while j >= 4:
					s += s4
					j -= 4
				if j == 1:
					s1 += s
					print(s1)
				elif j == 2:
					s2 += s
					print(s2)
				elif j == 3:
					s3 += s
					print(s3)
				elif j == 0:
					print(s)
		if k == 2:
			mn = 0
			s = ''
			s1 = '1'
			s2 = '01'
			s3 = '001'
			s4 = '0001'
			s5 = '01001'
			s6 = '001001'
			s7 = '0010110'
			s8 = '01101001'
			s9 = '100111010'
			s10 = '0111000101'
			s11 = '01000111010'
			s12 = '000000001101'
			s13 = '0101010100101'
			s14 = '10110100100011'
			if n == 1:
				mn = 1
				print(mn)
				print(s1)
			elif n == 2:
				mn = 3
				print(mn)
				print(s2)
			elif n == 3:
				mn = 4
				print(mn)
				print(s3)
			elif n == 4:
				mn = 2
				print(mn)
				print(s4)
			elif n == 5:
				mn = 3
				print(mn)
				print(s5)
			elif n == 6:
				mn = 1
				print(mn)
				print(s6)
			else:
				if n % 4 == 1 or n % 4 == 2:
					mn = 1
				else:
					mn = 0
				print(mn)
				if n == 7:
					print(s7)
				elif n == 8:
					print(s8)
				elif n == 9:
					print(s9)
				elif n == 10:
					print(s10)
				elif n == 11:
					print(s11)
				elif n == 12:
					print(s12)
				elif n == 13:
					print(s13)
				elif n == 14:
					print(s14)
				else:
					j = n
					while j > 14:
						s += '01101001'
						j -= 8
					if j == 1:
						s1 += s
						print(s1)
					elif j == 2:
						s2 += s
						print(s2)
					elif j == 3:
						s3 += s
						print(s3)
					elif j == 4:
						s4 += s
						print(s4)
					elif j == 5:
						s5 += s
						print(s5)
					elif j == 6:
						s6 += s
						print(s6)
					elif j == 7:
						s7 += s
						print(s7)
					elif j == 8:
						s8 += s
						print(s8)
					elif j == 9:
						s9 += s
						print(s9)
					elif j == 10:
						s10 += s
						print(s10)
					elif j == 11:
						s11 += s
						print(s11)
					elif j == 12:
						s12 += s
						print(s12)
					elif j == 13:
						s13 += s
						print(s13)
					elif j == 14:
						s14 += s
						print(s14)
		if k == 3:
			mn = 0
			s = ''
			s1 = '1'
			s2 = '01'
			s3 = '001'
			s4 = '0001'
			s5 = '00001'
			s6 = '011110'
			s7 = '0001110'
			s8 = '00110110'
			s9 = '011010110'
			s10 = '1111111010'
			s11 = '00001101001'
			s12 = '001011100110'
			s13 = '0000111011010'
			s14 = '01011001101001'
			s15 = '001111010111100'
			s16 = '0110100110010110'
			s17 = '10010110111110010'
			s18 = '010011010101011010'
			s19 = '1100110110100111100'
			s20 = '01011111110111111000'
			s21 = '001010011111111010010'
			s22 = '0001000111111101111000'
			s23 = '10001111101111110111000'
			s24 = '101011110110111110111000'
			s25 = '0001111011111111111110000'
			s26 = '01111111001101111111101000'
			s27 = '011101101111111011111110000'
			if n == 1:
				print(1)
				print(s1)
			elif n == 2:
				print(7)
				print(s2)
			elif n == 3:
				print(18)
				print(s3)
			elif n == 4:
				print(28)
				print(s4)
			elif n == 5:
				print(25)
				print(s5)
			elif n == 6:
				print(7)
				print(s6)
			elif n == 7:
				print(26)
				print(s7)
			elif n == 8:
				print(4)
				print(s8)
			elif n == 9:
				print(5)
				print(s9)
			elif n == 10:
				print(1)
				print(s10)
			elif n == 11:
				print(12)
				print(s11)
			elif n == 12:
				print(0)
				print(s12)
			else:
				if n % 4 == 1 or n % 4 == 2:
					mn = 1
				else:
					mn = 0
				print(mn)
				if n == 13:
					print(s13)
				elif n == 14:
					print(s14)
				elif n == 15:
					print(s15)
				elif n == 16:
					print(s16)
				elif n == 17:
					print(s17)
				elif n == 18:
					print(s18)
				elif n == 19:
					print(s19)
				elif n == 20:
					print(s20)
				elif n == 21:
					print(s21)
				elif n == 22:
					print(s22)
				elif n == 23:
					print(s23)
				elif n == 24:
					print(s24)
				elif n == 25:
					print(s25)
				elif n == 26:
					print(s26)
				elif n == 27:
					print(s27)
				else:
					j = n
					while j > 27:
						s += '0110100110010110'
						j -= 16
					if j == 1:
						s1 += s
						print(s1)
					elif j == 2:
						s2 += s
						print(s2)
					elif j == 3:
						s3 += s
						print(s3)
					elif j == 4:
						s4 += s
						print(s4)
					elif j == 5:
						s5 += s
						print(s5)
					elif j == 6:
						s6 += s
						print(s6)
					elif j == 7:
						s7 += s
						print(s7)
					elif j == 8:
						s8 += s
						print(s8)
					elif j == 9:
						s9 += s
						print(s9)
					elif j == 10:
						s10 += s
						print(s10)
					elif j == 11:
						s11 += s
						print(s11)
					elif j == 12:
						s12 += s
						print(s12)
					elif j == 13:
						s13 += s
						print(s13)
					elif j == 14:
						s14 += s
						print(s14)
					elif j == 15:
						s15 += s
						print(s15)
					elif j == 16:
						s16 += s
						print(s16)
					elif j == 17:
						s17 += s
						print(s17)
					elif j == 18:
						s18 += s
						print(s18)
					elif j == 19:
						s19 += s
						print(s19)
					elif j == 20:
						s20 += s
						print(s20)
					elif j == 21:
						s21 += s
						print(s21)
					elif j == 22:
						s22 += s
						print(s22)
					elif j == 23:
						s23 += s
						print(s23)
					elif j == 24:
						s24 += s
						print(s24)
					elif j == 25:
						s25 += s
						print(s25)
					elif j == 26:
						s26 += s
						print(s26)
					elif j == 27:
						s27 += s
						print(s27)
		if k == 4:
			mn = 0
			s = ''
			s1 = '1'
			s2 = '01'
			s3 = '001'
			s4 = '0001'
			s5 = '00001'
			s6 = '000001'
			s7 = '0000001'
			s8 = '00101110'
			s9 = '000001110'
			s10 = '0101001001'
			s11 = '00000101001'
			s12 = '001101010110'
			s13 = '0010110101001'
			s14 = '00000001111010'
			s15 = '011110001010110'
			s16 = '0000111000001110'
			s17 = '00101000011111100'
			s18 = '000000110100001110'
			s19 = '1000010010110111100'
			s20 = '00001010110111011100'
			s21 = '000000000100100100011'
			s22 = '1101001111011111110100'
			s23 = '00001000100110111101100'
			s24 = '000010011110110111110100'
			s25 = '0101110101111110111111000'
			s26 = '00010100000100010000110101'
			s27 = '001111000000011110111111000'
			s28 = '0001011111000101111011111000'
			s29 = '01010100010001011111010101010'
			s30 = '010110010011011011111111011000'
			s31 = '1111111111110100000010000101011'
			s32 = '01101001100101101001011001101001'
			s33 = '111111111101110101000011110101010'
			s34 = '1111101111111011111010101111100010'
			s35 = '11111111110101010011110100101101010'
			s36 = '111111111111011110000100000101000111'
			s37 = '1111111110101111111111101001101000101'
			s38 = '11111111111111010001100001010110010101'
			s39 = '111111111111111001010100010111010100110'
			s40 = '1111111111111101010110100001000101000111'
			s41 = '11111111111111110001010101100100010111010'
			s42 = '111111111111111111101101111111111001101000'
			s43 = '1111111111111111010000010000000001111001110'
			s44 = '11111111111111111000001001010001010011010101'
			s45 = '111111111111111111101011011111111001101100100'
			s46 = '1111111111111111110001100000010000010111010101'
			s47 = '11111111111111111101010100100001000101010110110'
			s48 = '111111111111111111011101000100010101100110010101'
			s49 = '1111111111111111111101010101000001110100010111010'
			s50 = '11111111111111111111111111111111101101010011100100'
			s51 = '111111111111111111110001010111000111010101010101001'
			s52 = '1111111111111111111101010000001000010101011001000111'
			s53 = '11111111111111111111111111111110001101011010100101001'
			s54 = '111111111111111111111101000110000001001101010101010101'
			s55 = '1111111111111111111111010100110101110100110101010101010'
			s56 = '00000001000001000011110111111111011111111111111110000000'
			s57 = '010001011101010111010111110111111111011111111111110000000'
			s58 = '0010111101100111110111111111111111111111111011111110000000'
			s59 = '00000101000100010111010111111111111111111111101111110000000'
			s60 = '000100010101010000110101111111111111111111111111011110000000'
			s61 = '1110100011011010101010110010111100111110011011111011011010000'
			if n == 1:
				print(1)
				print(s1)
			elif n == 2:
				print(15)
				print(s2)
			elif n == 3:
				print(64)
				print(s3)
			elif n == 4:
				print(158)
				print(s4)
			elif n == 5:
				print(271)
				print(s5)
			elif n == 6:
				print(317)
				print(s6)
			elif n == 7:
				print(126)
				print(s7)
			elif n == 8:
				print(34)
				print(s8)
			elif n == 9:
				print(253)
				print(s9)
			elif n == 10:
				print(13)
				print(s10)
			elif n == 11:
				print(92)
				print(s11)
			elif n == 12:
				print(30)
				print(s12)
			elif n == 13:
				print(47)
				print(s13)
			elif n == 14:
				print(31)
				print(s14)
			elif n == 15:
				print(2)
				print(s15)
			elif n == 16:
				print(0)
				print(s16)
			elif n == 17:
				print(1)
				print(s17)
			elif n == 18:
				print(13)
				print(s18)
			elif n == 19:
				print(0)
				print(s19)
			elif n == 20:
				print(0)
				print(s20)
			elif n == 21:
				print(9)
				print(s21)
			elif n == 22:
				print(1)
				print(s22)
			elif n == 23:
				print(0)
				print(s23)
			elif n == 24:
				print(0)
				print(s24)
			elif n == 25:
				print(1)
				print(s25)
			elif n == 26:
				print(5)
				print(s26)
			elif n == 27:
				print(0)
				print(s27)
			elif n == 28:
				print(0)
				print(s28)
			elif n == 29:
				print(5)
				print(s29)
			elif n == 30:
				print(1)
				print(s30)
			else:
				if n % 4 == 1 or n % 4 == 2:
					mn = 1
				else:
					mn = 0
				print(mn)
				if n == 31:
					print(s31)
				elif n == 32:
					print(s32)
				elif n == 33:
					print(s33)
				elif n == 34:
					print(s34)
				elif n == 35:
					print(s35)
				elif n == 36:
					print(s36)
				elif n == 37:
					print(s37)
				elif n == 38:
					print(s38)
				elif n == 39:
					print(s39)
				elif n == 40:
					print(s40)
				elif n == 41:
					print(s41)
				elif n == 42:
					print(s42)
				elif n == 43:
					print(s43)
				elif n == 44:
					print(s44)
				elif n == 45:
					print(s45)
				elif n == 46:
					print(s46)
				elif n == 47:
					print(s47)
				elif n == 48:
					print(s48)
				elif n == 49:
					print(s49)
				elif n == 50:
					print(s50)
				elif n == 51:
					print(s51)
				elif n == 52:
					print(s52)
				elif n == 53:
					print(s53)
				elif n == 54:
					print(s54)
				elif n == 55:
					print(s55)
				elif n == 56:
					print(s56)
				elif n == 57:
					print(s57)
				elif n == 58:
					print(s58)
				elif n == 59:
					print(s59)
				elif n == 60:
					print(s60)
				elif n == 61:
					print(s61)
				else:
					j = n
					while j > 61:
						s += s32
						j -= 32
					if j == 1:
						s1 += s
						print(s1)
					elif j == 2:
						s2 += s
						print(s2)
					elif j == 3:
						s3 += s
						print(s3)
					elif j == 4:
						s4 += s
						print(s4)
					elif j == 5:
						s5 += s
						print(s5)
					elif j == 6:
						s6 += s
						print(s6)
					elif j == 7:
						s7 += s
						print(s7)
					elif j == 8:
						s8 += s
						print(s8)
					elif j == 9:
						s9 += s
						print(s9)
					elif j == 10:
						s10 += s
						print(s10)
					elif j == 11:
						s11 += s
						print(s11)
					elif j == 12:
						s12 += s
						print(s12)
					elif j == 13:
						s13 += s
						print(s13)
					elif j == 14:
						s14 += s
						print(s14)
					elif j == 15:
						s15 += s
						print(s15)
					elif j == 16:
						s16 += s
						print(s16)
					elif j == 17:
						s17 += s
						print(s17)
					elif j == 18:
						s18 += s
						print(s18)
					elif j == 19:
						s19 += s
						print(s19)
					elif j == 20:
						s20 += s
						print(s20)
					elif j == 21:
						s21 += s
						print(s21)
					elif j == 22:
						s22 += s
						print(s22)
					elif j == 23:
						s23 += s
						print(s23)
					elif j == 24:
						s24 += s
						print(s24)
					elif j == 25:
						s25 += s
						print(s25)
					elif j == 26:
						s26 += s
						print(s26)
					elif j == 27:
						s27 += s
						print(s27)
					elif j == 28:
						s28 += s
						print(s28)
					elif j == 29:
						s29 += s
						print(s29)
					elif j == 30:
						s30 += s
						print(s30)
					elif j == 31:
						s31 += s
						print(s31)
					elif j == 32:
						s32 += s
						print(s32)
					elif j == 33:
						s33 += s
						print(s33)
					elif j == 34:
						s34 += s
						print(s34)
					elif j == 35:
						s35 += s
						print(s35)
					elif j == 36:
						s36 += s
						print(s36)
					elif j == 37:
						s37 += s
						print(s37)
					elif j == 38:
						s38 += s
						print(s38)
					elif j == 39:
						s39 += s
						print(s39)
					elif j == 40:
						s40 += s
						print(s40)
					elif j == 41:
						s41 += s
						print(s41)
					elif j == 42:
						s42 += s
						print(s42)
					elif j == 43:
						s43 += s
						print(s43)
					elif j == 44:
						s44 += s
						print(s44)
					elif j == 45:
						s45 += s
						print(s45)
					elif j == 46:
						s46 += s
						print(s46)
					elif j == 47:
						s47 += s
						print(s47)
					elif j == 48:
						s48 += s
						print(s48)
					elif j == 49:
						s49 += s
						print(s49)
					elif j == 50:
						s50 += s
						print(s50)
					elif j == 51:
						s51 += s
						print(s51)
					elif j == 52:
						s52 += s
						print(s52)
					elif j == 53:
						s53 += s
						print(s53)
					elif j == 54:
						s54 += s
						print(s54)
					elif j == 55:
						s55 += s
						print(s55)
					elif j == 56:
						s56 += s
						print(s56)
					elif j == 57:
						s57 += s
						print(s57)
					elif j == 58:
						s58 += s
						print(s58)
					elif j == 59:
						s59 += s
						print(s59)
					elif j == 60:
						s60 += s
						print(s60)
					elif j == 61:
						s61 += s
						print(s61)
except:
	pass


def helper1(n):
	dp = [0] * n
	if n % 2 == 0:
		flag = -1
		for i in range(n // 2):
			dp[i] = flag
			flag *= -1
		if n // 2 % 2 != 0:
			dp[n // 2] = flag
			for i in range(n // 2 + 1, n):
				dp[i] = flag
				flag *= -1
		else:
			flag *= -1
			for i in range(n // 2, n):
				dp[i] = flag
				flag *= -1
	else:
		dp[0] = -1
		flag = -1
		for i in range(1, (n + 1) // 2):
			dp[i] = flag
			flag *= -1
		if (n - 1) // 2 % 2 != 0:
			dp[(n + 1) // 2] = flag
			for i in range((n + 1) // 2 + 1, n):
				dp[i] = flag
				flag *= -1
		else:
			flag *= -1
			for i in range((n + 1) // 2, n):
				dp[i] = flag
				flag *= -1
	sum1 = sum2 = 0
	b = ''
	for i in range(n):
		if dp[i] == -1:
			sum1 += i + 1
			b += '0'
		else:
			sum2 += i + 1
			b += '1'
	print(abs(sum1 - sum2))
	print(b)

def helper2(n):
	d = [['', 0], ['1', 1], ['01', 3], ['001', 4], ['0001', 2], ['01001', 3], ['101001', 1], ['1101001', 0], ['01101001', 0], ['011000101', 1], ['0100100101', 1], ['10111000101', 0], ['000000001101', 0], ['0001000010011', 1]]
	if n < 14:
		print(d[n][1])
		print(d[n][0])
	else:
		r = n % 8
		temp = n // 8
		if r < 6:
			r += 8
			temp -= 1
		print(d[r][1])
		print(d[r][0] + d[8][0] * temp)

def helper3(n):
	d = [['', 0], ['1', 1], ['01', 7], ['001', 18], ['0001', 28], ['00001', 25], ['010001', 7], ['0001110', 26], ['00110110', 4], ['011010110', 5], ['1000000101', 1], ['00001101001', 12], ['110100011001', 0], ['0000010000011', 1], ['01011001101001', 1], ['110000101000011', 0], ['1001011001101001', 0], ['11101001000001101', 1], ['010011010101011010', 1], ['0011001001011000011', 0], ['10100000001000000111', 0], ['011000000001010010011', 1], ['0000000000000001000111', 1], ['01110000010000001000111', 0], ['010100001001000001000111', 0], ['0000000001001000000100111', 1], ['01001100101000000000001111', 1], ['100010010000000100000001111', 0]]
	if n < 28:
		print(d[n][1])
		print(d[n][0])
	else:
		r = n % 16
		temp = n // 16
		if r < 12:
			r += 16
			temp -= 1
		print(d[r][1])
		print(d[r][0] + d[16][0] * temp)

def helper4(n):
	d = [['', 0], ['1', 1], ['01', 15], ['001', 64], ['0001', 158], ['00001', 271], ['000001', 317], ['0000001', 126], ['00101110', 34], ['000001110', 253], ['0101001001', 13], ['00000101001', 92], ['001101010110', 30], ['0010110101001', 47], ['00000001111010', 31], ['011110001010110', 2], ['1111000111110001', 0], ['01111000000010101', 1], ['000000110100001110', 13], ['0111101101001000011', 0], ['11110101001000100011', 0], ['000000000100100100011', 9], ['1010110000100000001011', 1], ['11110111011001000010011', 0], ['111101100001001000001011', 0], ['0111001010100010000000111', 1], ['00010100000100010000110101', 5], ['110000111111100001000000111', 0], ['1110100000111010000100000111', 0], ['00010000000100110001000101110', 5], ['011101101110101000000000100111', 1], ['0010011110001000100000000010111', 0], ['01101001100101101001011001101001', 0], ['101101001100101101001011001101001', 1], ['0101010001000000000100010000010111', 1], ['10111000110100101000000010000001111', 0], ['011010101011100010000000000100001111', 0], ['0000000101000100000001000000000111011', 1], ['01101011011010100000001000000010001111', 1], ['111111011011101000001000000000000101111', 0], ['1111110110110011101000000000000000011111', 0], ['10111010101001100000000000100000000011111', 1], ['100000010000000101000001010000000000011111', 1], ['1110101100111110001000000000000100000011111', 0], ['01011011000001110010011001101000100001101110', 0], ['111111111111111111101011011111111001101100100', 1], ['0000000000000000001110011111101111101000101010', 1], ['00000000000000000010101011011110111010101001001', 0], ['111100011111000101101001100101101001011001101001', 0], ['0111100000001010110010110011010010110100110010110', 1], ['00000000000000000000000000000000010010101100011011', 1], ['011110110100100001110010110011010010110100110010110', 0], ['1111010100100010001110010110011010010110100110010110', 0], ['11111111111111111111111111111110001101011010100101001', 1], ['101011000010000000101110010110011010010110100110010110', 1], ['1111011101100100001001110010110011010010110100110010110', 0], ['11110110000100100000101110010110011010010110100110010110', 0], ['011100101010001000000011110010110011010010110100110010110', 1], ['1101000010011000001000000000000000000000000100000001111111', 1], ['11000011111110000100000011110010110011010010110100110010110', 0], ['111010000011101000010000011110010110011010010110100110010110', 0], ['1110100011011010101010110010111100111110011011111011011010000', 1]]
	if n < 62:
		print(d[n][1])
		print(d[n][0])
	else:
		r = n % 32
		temp = n // 32
		if r < 30:
			r += 32
			temp -= 1
		print(d[r][1])
		print(d[r][0] + d[32][0] * temp)
k = int(input())
t = int(input())
for _ in range(t):
	n = int(input())
	if k == 1:
		helper1(n)
	elif k == 2:
		helper2(n)
	elif k == 3:
		helper3(n)
	else:
		helper4(n)


def common(mydict, n):
	size = len(mydict)
	index = n % size
	print(mydict[index][0])
	if index != 0:
		print(mydict[index][1], end='')
	print(mydict[0][1] * (n // size))

def forkeq4(n):
	dic = [(1, '1'), (15, '01'), (64, '001'), (158, '0001'), (271, '00001'), (317, '000001'), (126, '0000001'), (34, '11010001'), (253, '000001110'), (13, '0101001001'), (92, '00000101001'), (30, '110010101001'), (47, '0010110101001'), (31, '11111110000101'), (2, '100001110101001'), (0, '1111000111110001'), (1, '11010111100000011'), (13, '111111001011110001'), (0, '0111101101001000011'), (0, '11110101001000100011'), (9, '000000000100100100011'), (1, '1010110000100000001011'), (0, '11110111011001000010011'), (0, '111101100001001000001011'), (1, '1010001010000001000000111'), (5, '00010100000100010000110101'), (0, '110000111111100001000000111'), (0, '1110100000111010000100000111'), (5, '10101011101110100000101010101'), (1, '111111100001110000000100011110'), (0, '1111100011010010000011001100011'), (0, '01101001100101101001011001101001'), (1, '111111110010001000000101001001011'), (1, '0000010000000100000101010000011101'), (0, '11111111010000001010000000110110110'), (0, '111111111000010110000000001100101101'), (1, '1111110010101110101010101000101010101'), (1, '10010011001001101001011100110000111001'), (0, '111111111100011100000000000000111000111'), (0, '1111111111100000001001001001000011000111'), (1, '10000100001000100000001110101110111100010'), (1, '000000010000000101000001010000000000011111'), (0, '1111111111000100000000001001001010100101101'), (0, '11111111111101000011000000000000001110101101'), (1, '010000010000010000000101000000000001000011111'), (1, '0010101001000010011010110101111101011101011000'), (0, '10100011011000100101110010011001110110111101000'), (0, '111001100000100010110101010011111111110111010000'), (1, '1000110001000000000000101100111111111110111100000'), (1, '10101010101110000110111101111111101011111011001000'), (0, '110101010010001000001111001111101111011101111100000'), (0, '0000101000010000011010110101110011111111111111000000'), (1, '10100011001111111010101010111111001110110010111110000'), (1, '110101010000110010101001100001010101111111111011100000'), (0, '0110010111000000100101101000110111111111111011110100000'), (0, '11000101100011011001101100000111001111011111111111000000'), (1, '110001100010000101010110110101011111111110011111111000000'), (1, '0110101010001010101011110111111011100011111011111111000000'), (0, '10111100001000011101010101011111011111011111111111110000000'), (0, '011001010100110011111010010011010001111111111111111101000000'), (1, '1010101011101010100011001111111011011101011111111111101000000')]
	if n < 62:
		print(dic[n - 1][0])
		print(dic[n - 1][1])
		return
	value = n % 32
	if value < 30:
		value += 32
	m = (n - value) // 32
	print(dic[value - 1][0])
	print(dic[value - 1][1] + '01101001100101101001011001101001' * m)

def forkeq3(n):
	dic = [(1, '0'), (7, '01'), (18, '001'), (28, '0001'), (25, '00001'), (7, '010001'), (26, '0001110'), (4, '00110110'), (5, '011010110'), (1, '0000000101'), (12, '00001101001'), (0, '001011100110'), (1, '0000010000011'), (1, '01011001101001'), (0, '001011001101001'), (0, '0110100110010110'), (1, '00010110111110010'), (1, '010011010101011010'), (0, '0011001001011000011'), (0, '00000001010101100110'), (1, '000010010010110010110'), (1, '0000000000000001000111'), (0, '00000000011010001100011'), (0, '000000000000101011110001'), (1, '0000000000001101011110010'), (1, '00000000001101001101101010'), (0, '000000000001001111110111000')]
	if n < 28:
		print(dic[n - 1][0])
		print(dic[n - 1][1])
		return
	value = n % 16
	if value < 12:
		value += 16
	m = (n - value) // 16
	print(dic[value - 1][0])
	print(dic[value - 1][1] + '0110100110010110' * m)

def forkeq2(n):
	dic = [(1, '0'), (3, '01'), (4, '001'), (2, '0001'), (3, '01001'), (1, '001001'), (0, '0010110'), (0, '01101001'), (1, '000011001'), (1, '0100100101'), (0, '01000111010'), (0, '000000001101'), (1, '0000000110110')]
	if n < 14:
		print(dic[n - 1][0])
		print(dic[n - 1][1])
		return
	value = n % 8
	if value < 6:
		value += 8
	m = (n - value) // 8
	print(dic[value - 1][0])
	print(dic[value - 1][1] + '01101001' * m)

def forkeq1(n):
	mydict = [(0, '1001'), (1, '1'), (1, '10'), (0, '110')]
	common(mydict, n)
k = int(input())
t = int(input())
for _ in range(t):
	n = int(input())
	if k == 1:
		forkeq1(n)
	if k == 2:
		forkeq2(n)
	if k == 3:
		forkeq3(n)
	if k == 4:
		forkeq4(n)


k = int(input())
for _ in range(int(input())):
	n = int(input())
	if k == 1:
		s = '0110' * (n // 4)
		if n % 4 == 0:
			print(0)
			print(s)
		if n % 4 == 1:
			print(1)
			print('1' + s)
		if n % 4 == 2:
			print(1)
			print('01' + s)
		if n % 4 == 3:
			print(0)
			print('001' + s)
	if k == 2:
		c = n // 8 - 1
		s = '01101001'
		if n == 1:
			print(1)
			print('1')
		if n == 2:
			print(3)
			print('01')
		if n == 3:
			print(4)
			print('001')
		if n == 4:
			print(2)
			print('0001')
		if n == 5:
			print(3)
			print('01001')
		if n == 6:
			print(1)
			print('001001')
		if n == 7:
			print(0)
			print('0010110')
		if n >= 8:
			m = n % 8
			if m == 0:
				print(0)
				print(s * (c + 1))
			if m == 1:
				print(1)
				print('0' + s * (c + 1))
			if m == 2:
				print(1)
				print('0111000101' + s * c)
			if m == 3:
				print(0)
				print('10111000101' + s * c)
			if m == 4:
				print(0)
				print('010111000101' + s * c)
			if m == 5:
				print(1)
				print('1010001011001' + s * c)
			if m == 6:
				print(1)
				print('001001' + s * (c + 1))
			if m == 7:
				print(0)
				print('0010110' + s * (c + 1))
	if k == 3:
		s = '1001011001101001'
		c = n // 16 - 1
		if n == 1:
			print(1)
			print('1')
		if n == 2:
			print(7)
			print('01')
		if n == 3:
			print(18)
			print('001')
		if n == 4:
			print(28)
			print('0001')
		if n == 5:
			print(25)
			print('00001')
		if n == 6:
			print(7)
			print('010001')
		if n == 7:
			print(26)
			print('1110001')
		if n == 8:
			print(4)
			print('11001001')
		if n == 9:
			print(5)
			print('100101001')
		if n == 10:
			print(1)
			print('1000000101')
		if n == 11:
			print(12)
			print('00001101001')
		if n == 12:
			print(0)
			print('001011100110')
		if n == 13:
			print(1)
			print('0000010000011')
		if n == 14:
			print(1)
			print('01011001101001')
		if n == 15:
			print(0)
			print('110000101000011')
		if n >= 16:
			m = n % 16
			if m == 0:
				print(0)
				print(s * (c + 1))
			if m == 1:
				print(1)
				print('11101001000001101' + s * c)
			if m == 2:
				print(1)
				print('101100101010100101' + s * c)
			if m == 3:
				print(0)
				print('0011001001011000011' + s * c)
			if m == 4:
				print(0)
				print('10100000001000000111' + s * c)
			if m == 5:
				print(1)
				print('011000000001010010011' + s * c)
			if m == 6:
				print(1)
				print('0000000000000001000111' + s * c)
			if m == 7:
				print(0)
				print('01110000010000001000111' + s * c)
			if m == 8:
				print(0)
				print('010100001001000001000111' + s * c)
			if m == 9:
				print(1)
				print('1110000100000000000001111' + s * c)
			if m == 10:
				print(1)
				print('10000001011001011001101001' + s * c)
			if m == 11:
				print(0)
				print('100010010000000100000001111' + s * c)
			if m == 12:
				print(0)
				print('1101000110011001011001101001' + s * c)
			if m == 13:
				print(1)
				print('00000100000111001011001101001' + s * c)
			if m == 14:
				print(1)
				print('010110011010011001011001101001' + s * c)
			if m == 15:
				print(0)
				print('1100001010000111001011001101001' + s * c)
	if k == 4:
		s = '01101001100101101001011001101001'
		c = n // 32 - 1
		if n == 1:
			print(1)
			print('1')
		if n == 2:
			print(15)
			print('01')
		if n == 3:
			print(64)
			print('001')
		if n == 4:
			print(158)
			print('0001')
		if n == 5:
			print(271)
			print('00001')
		if n == 6:
			print(317)
			print('000001')
		if n == 7:
			print(126)
			print('0000001')
		if n == 8:
			print(34)
			print('11010001')
		if n == 9:
			print(253)
			print('000001110')
		if n == 10:
			print(13)
			print('0101001001')
		if n == 11:
			print(92)
			print('00000101001')
		if n == 12:
			print(30)
			print('110010101001')
		if n == 13:
			print(47)
			print('0010110101001')
		if n == 14:
			print(31)
			print('11111110000101')
		if n == 15:
			print(2)
			print('100001110101001')
		if n == 16:
			print(0)
			print('1111000111110001')
		if n == 17:
			print(1)
			print('11010111100000011')
		if n == 18:
			print(13)
			print('111111001011110001')
		if n == 19:
			print(0)
			print('0111101101001000011')
		if n == 20:
			print(0)
			print('11110101001000100011')
		if n == 21:
			print(9)
			print('000000000100100100011')
		if n == 22:
			print(1)
			print('1010110000100000001011')
		if n == 23:
			print(0)
			print('11110111011001000010011')
		if n == 24:
			print(0)
			print('111101100001001000001011')
		if n == 25:
			print(1)
			print('1010001010000001000000111')
		if n == 26:
			print(5)
			print('00010100000100010000110101')
		if n == 27:
			print(0)
			print('110000111111100001000000111')
		if n == 28:
			print(0)
			print('1110100000111010000100000111')
		if n == 29:
			print(5)
			print('10101011101110100000101010101')
		if n == 30:
			print(1)
			print('111111100001110000000100011110')
		if n == 31:
			print(0)
			print('1111100011010010000011001100011')
		if n >= 32:
			m = n % 32
			if m == 0:
				print(0)
				print(s * (c + 1))
			if m == 1:
				print(1)
				print('111111110010001000000101001001011' + s * c)
			if m == 2:
				print(1)
				print('0000010000000100000101010000011101' + s * c)
			if m == 3:
				print(0)
				print('11111111010000001010000000110110110' + s * c)
			if m == 4:
				print(0)
				print('111111111000010110000000001100101101' + s * c)
			if m == 5:
				print(1)
				print('1111110010101110101010101000101010101' + s * c)
			if m == 6:
				print(1)
				print('10010011001001101001011100110000111001' + s * c)
			if m == 7:
				print(0)
				print('111111111100011100000000000000111000111' + s * c)
			if m == 8:
				print(0)
				print('1111111111100000001001001001000011000111' + s * c)
			if m == 9:
				print(1)
				print('10000100001000100000001110101110111100010' + s * c)
			if m == 10:
				print(1)
				print('000000010000000101000001010000000000011111' + s * c)
			if m == 11:
				print(0)
				print('1111111111000100000000001001001010100101101' + s * c)
			if m == 12:
				print(0)
				print('11111111111101000011000000000000001110101101' + s * c)
			if m == 13:
				print(1)
				print('010000010000010000000101000000000001000011111' + s * c)
			if m == 14:
				print(1)
				print('0010101001000010011010110101111101011101011000' + s * c)
			if m == 15:
				print(0)
				print('10100011011000100101110010011001110110111101000' + s * c)
			if m == 16:
				print(0)
				print('111001100000100010110101010011111111110111010000' + s * c)
			if m == 17:
				print(1)
				print('1000110001000000000000101100111111111110111100000' + s * c)
			if m == 18:
				print(1)
				print('10101010101110000110111101111111101011111011001000' + s * c)
			if m == 19:
				print(0)
				print('110101010010001000001111001111101111011101111100000' + s * c)
			if m == 20:
				print(0)
				print('0000101000010000011010110101110011111111111111000000' + s * c)
			if m == 21:
				print(1)
				print('10100011001111111010101010111111001110110010111110000' + s * c)
			if m == 22:
				print(1)
				print('110101010000110010101001100001010101111111111011100000' + s * c)
			if m == 23:
				print(0)
				print('0110010111000000100101101000110111111111111011110100000' + s * c)
			if m == 24:
				print(0)
				print('11000101100011011001101100000111001111011111111111000000' + s * c)
			if m == 25:
				print(1)
				print('110001100010000101010110110101011111111110011111111000000' + s * c)
			if m == 26:
				print(1)
				print('0110101010001010101011110111111011100011111011111111000000' + s * c)
			if m == 27:
				print(0)
				print('10111100001000011101010101011111011111011111111111110000000' + s * c)
			if m == 28:
				print(0)
				print('011001010100110011111010010011010001111111111111111101000000' + s * c)
			if m == 29:
				print(1)
				print('1010101011101010100011001111111011011101011111111111101000000' + s * c)
			if m == 30:
				print(1)
				print('01010100000001100100100111011101111011111111111101111110000000' + s * c)
			if m == 31:
				print(0)
				print('110100110000100000010101101011110111011111111111110111110000000' + s * c)


def solve_1():
	for _ in range(int(input())):
		N = int(input())
		if N % 4 == 0:
			print(0)
			print('1001' * (N // 4))
		elif N % 4 == 1:
			print(1)
			print('1' + '1001' * (N // 4))
		elif N % 4 == 2:
			print(1)
			print('10' + '1001' * (N // 4))
		elif N % 4 == 3:
			print(0)
			print('110' + '1001' * (N // 4))

def solve_2():
	array = [[0, ''], [1, '0'], [3, '01'], [4, '001'], [2, '0001'], [3, '01001'], [1, '001001'], [0, '0010110'], [0, '01101001'], [1, '000011001'], [1, '0100100101'], [0, '01000111010'], [0, '000000001101'], [1, '0000000110110'], [1, '00000011100110'], [0, '000000101011001'], [0, '0000100011100110'], [1, '00000000111011100'], [1, '000000000001110110'], [0, '0000000001001111100'], [0, '00000000001011100101']]
	for _ in range(int(input())):
		N = int(input())
		if N <= 20:
			print(array[N][0])
			print(array[N][1])
		else:
			rem = N % 8
			rem += 8
			q = (N - rem) // 8
			print(array[rem][0])
			print(array[rem][1] + '01101001' * q)

def solve_3():
	array = [[0, ''], [1, '0'], [7, '01'], [18, '001'], [28, '0001'], [25, '00001'], [7, '010001'], [26, '0001110'], [4, '00110110'], [5, '011010110'], [1, '0000000101'], [12, '00001101001'], [0, '001011100110'], [1, '0000010000011'], [1, '01011001101001'], [0, '001011001101001'], [0, '0110100110010110'], [1, '00010110111110010'], [1, '010011010101011010'], [0, '0011001001011000011'], [0, '00000001010101100110'], [1, '000010010010110010110'], [1, '0000000000000001000111'], [0, '00000000011010001100011'], [0, '000000000000101011110001'], [1, '0000000000001101011110010'], [1, '00000000001101001101101010'], [0, '000000000001001111110111000'], [0, '0000000000100100010010110110'], [1, '00000000000001101000001111001'], [1, '000000000001000011010011011010'], [0, '0000000000011001101001010001011']]
	for _ in range(int(input())):
		N = int(input())
		if N < 32:
			print(array[N][0])
			print(array[N][1])
		else:
			rem = N % 16
			rem += 16
			q = (N - rem) // 16
			print(array[rem][0])
			print(array[rem][1] + '0110100110010110' * q)

def solve_4():
	final = {1: [1, '0'], 2: [15, '01'], 3: [64, '001'], 4: [158, '0001'], 5: [271, '00001'], 6: [317, '000001'], 7: [126, '0000001'], 8: [34, '00101110'], 9: [253, '000001110'], 10: [13, '0101001001'], 11: [92, '00000101001'], 12: [30, '001101010110'], 13: [47, '0010110101001'], 14: [31, '00000001111010'], 15: [2, '011110001010110'], 16: [0, '0000111000001110'], 17: [1, '00000010110010110'], 18: [13, '000000110100001110'], 19: [0, '0001100111111001001'], 20: [0, '00001010110111011100'], 21: [9, '000000000100100100011'], 22: [1, '0000100101101110000011'], 23: [0, '00000011011000111011100'], 24: [0, '000000100111111111100001'], 25: [1, '0000000010101011110000011'], 26: [5, '00010100000100010000110101'], 27: [0, '000000101010110011001101001'], 28: [0, '0000000010001100101111111000'], 29: [5, '11101111111011001110111010001'], 30: [1, '000000000010100011011110101100'], 31: [0, '0000000000001011111101111010100'], 32: [0, '01101001100101101001011001101001'], 33: [1, '001101001100101101001011001101001'], 34: [1, '1010101110111111111011101111101000'], 35: [0, '01000111001011010111111101111110000'], 36: [0, '000000000000100001111011111010111000'], 37: [1, '1111111010111011111110111111111000100'], 38: [1, '10010100100101011111110111111101110000'], 39: [0, '000000100100010111110111111111111010000'], 40: [0, '0000001001001100010111111111111111100000'], 41: [1, '01000101010110011111111111011111111100000'], 42: [1, '011111101111111010111110101111111111100000'], 43: [0, '0001010011000001110111111111111011111100000'], 44: [0, '00000100000101011110111111111111110111100000'], 45: [1, '001111101111101111111010111111111110111100000'], 46: [1, '0110010100010101010110111111111111111101100000'], 47: [0, '01010100000101010111101111111111111111111000000'], 48: [0, '000011100000111001101001100101101001011001101001'], 49: [1, '0000001011001011001101001100101101001011001101001'], 50: [1, '01010100000100000000010101010001010101000111101010'], 51: [0, '000110011111100100101101001100101101001011001101001'], 52: [0, '0000101011011101110001101001100101101001011001101001'], 53: [1, '00110000100001100001000101010011000101010001010101110'], 54: [1, '000010010110111000001101101001100101101001011001101001'], 55: [0, '0000001101100011101110001101001100101101001011001101001'], 56: [0, '00000010011111111110000101101001100101101001011001101001'], 57: [1, '000000001010101111000001101101001100101101001011001101001'], 58: [1, '1111001100000000000001010001000110010111110101010001010101'], 59: [0, '00000010101011001100110100101101001100101101001011001101001'], 60: [0, '000000001000110010111111100001101001100101101001011001101001'], 61: [1, '1010100010010010000011010000010101010101000101010101110101010'], 62: [1, '00000000001010001101111010110001101001100101101001011001101001'], 63: [0, '000000000000101111110111101010001101001100101101001011001101001'], 64: [0, '0110100110010110100101100110100101101001100101101001011001101001']}
	for _ in range(int(input())):
		N = int(input())
		if N < 64:
			print(final[N][0])
			print(final[N][1])
		else:
			rem = N % 32
			rem += 32
			q = (N - rem) // 32
			print(final[rem][0])
			print(final[rem][1] + '01101001100101101001011001101001' * q)
K = int(input())
if K == 1:
	solve_1()
elif K == 2:
	solve_2()
elif K == 3:
	solve_3()
else:
	solve_4()