Chef loves saving money and he trusts none other bank than State Bank of Chefland. Unsurprisingly, the employees like giving a hard time to their customers. But instead of asking them to stand them in long queues, they have weird way of accepting money.
Chef did his homework and found that the bank only accepts the money in coins such that the sum of the denomination with any previously deposited coin OR itself can't be obtained by summing any two coins OR double of any coin deposited before. Considering it all, he decided to start with $1$ Chefland rupee and he would keep choosing smallest possible denominations upto $N$ coins. Since chef is busy with his cooking, can you find out the $N$ denomination of coins chef would have to take to the bank? Also find the total sum of money of those $N$ coins.

-----Input:-----
- First line has a single integer $T$ i.e. number of testcases.
- $T$ lines followed, would have a single integer $N$ i.e. the number of coins the chef is taking.

-----Output:-----
- Output for $i$-th testcase ($1 ≤ i ≤ T$) would have 2 lines.
- First line would contain $N$ integers i.e. the denomination of coins chef would deposit to the bank.
- Second line would contain a single integer i.e. the sum of all the coins chef would deposit.

-----Constraints:-----
- $1 ≤ T ≤ 700$
- $1 ≤ N ≤ 700$

-----Subtasks:-----
- $20$ points: $1 ≤ T, N ≤ 80$
- $70$ points: $1 ≤ T, N ≤ 500$
- $10$ points: $1 ≤ T, N ≤ 700$ 

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
1
1
1 2
3
1 2 4
7
1 2 4 8
15

-----Explanation:-----
For testcase 1: First coin is stated to be 1, hence for $N$ = 1, 1 is the answer.
For testcase 2: Since chef chooses the lowest possible denomination for each $i$-th coin upto $N$ coins, second coin would be 2. Only sum possible with N = 1 would be 1+1 = 2. For N = 2, $\{1+2,  2+2\}$ $\neq$ $2$.
For testcase 3: With first two coins being 1 and 2, next coin couldn't be 3 because 3+1 = 2+2, but $\{4+1,  4+2,  4+4\}$ $\neq$ $\{1+1,  1+2,  2+2\}$

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
lst = [1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851, 5123, 5243, 5298, 5751, 5998, 6374, 6801, 6925, 7460, 7547, 7789, 8220, 8503, 8730, 8942, 9882, 10200, 10587, 10898, 11289, 11614, 11876, 12034, 12931, 13394, 14047, 14534, 14901, 15166, 15688, 15972, 16619, 17355, 17932, 18845, 19071, 19631, 19670, 20722, 21948, 22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219, 28566, 29775, 30094, 31311, 32217, 32620, 32912, 34277, 35330, 35469, 36204, 38647, 39160, 39223, 39943, 40800, 41882, 42549, 43394, 44879, 45907, 47421, 47512, 48297, 50064, 50902, 52703, 52764, 54674, 55307, 56663, 58425, 59028, 60576, 60995, 62205, 63129, 64488, 66999, 67189, 68512, 68984, 70170, 71365, 75618, 76793, 77571, 79047, 80309, 83179, 84345, 87016, 87874, 88566, 89607, 91718, 92887, 93839, 95103, 97974, 99583, 101337, 102040, 103626, 104554, 106947, 107205, 108622, 111837, 112800, 113949, 114642, 116291, 117177, 121238, 125492, 126637, 129170, 130986, 131697, 134414, 134699, 136635, 139964, 143294, 144874, 146605, 147499, 148593, 150146, 152318, 152834, 156836, 157150, 160782, 163010, 163502, 164868, 170984, 172922, 174171, 177853, 180249, 182071, 185403, 188314, 190726, 190894, 193477, 196832, 199646, 201472, 202699, 205325, 206811, 208748, 214435, 217182, 218011, 225350, 226682, 229163, 231694, 233570, 234619, 235152, 238727, 240814, 247822, 253857, 254305, 260433, 261620, 262317, 266550, 269195, 271511, 274250, 274753, 280180, 284289, 290005, 293034, 295037, 296506, 298414, 302663, 305782, 308841, 317739, 321173, 323672, 324806, 329181, 331018, 336642, 340901, 343359, 347001, 348110, 348899, 362520, 366119, 368235, 370696, 371542, 377450, 380366, 382012, 382245, 384957, 387479, 390518, 391462, 399174, 403920, 411847, 412671, 416880, 417991, 422453, 433973, 434773, 440619, 441148, 443779, 446065, 456289, 458426, 462402, 470670, 474668, 475800, 481476, 482868, 498435, 501084, 508193, 511258, 514644, 524307, 527197, 535369, 536903, 538331, 542020, 555275, 564016, 566106, 567408, 572027, 582478, 583407, 585871, 593257, 596837, 598426, 599784, 607794, 610404, 621790, 624574, 627703, 633442, 640047, 648858, 659179, 663558, 667337, 672815, 673522, 686013, 691686, 693169, 694279, 696931, 703162, 711364, 723249, 729860, 731008, 739958, 740124, 744403, 753293, 768134, 770113, 773912, 779917, 787407, 794900, 797567, 800658, 813959, 814414, 827123, 829129, 839728, 847430, 850695, 851627, 862856, 880796, 884725, 889285, 896691, 897160, 904970, 909586, 915254, 922852, 935695, 937825, 938876, 959937, 961353, 964857, 970227, 976356, 980581, 986799, 1008106, 1009835, 1016906, 1020306, 1028612, 1033242, 1036012, 1042818, 1050881, 1051783, 1060844, 1086402, 1092043, 1096162, 1103456, 1123464, 1134057, 1136410, 1144080, 1145152, 1147774, 1156687, 1164278, 1166255, 1174751, 1187057, 1195316, 1201262, 1207345, 1212654, 1218610, 1225019, 1227887, 1240777, 1247071, 1258235, 1265462, 1274089, 1279515, 1288613, 1298980, 1306248, 1326918, 1333809, 1341190, 1343482, 1367480, 1372734, 1374779, 1384952, 1388147, 1394240, 1395346, 1409612, 1417336, 1418943, 1423296, 1446209, 1448494, 1462599, 1468933, 1474698, 1496110, 1502217, 1508335, 1513944, 1549693, 1552361, 1558304, 1567726, 1578307, 1593543, 1594370, 1596552, 1604567, 1611655, 1638201, 1657904, 1661549, 1668344, 1684653, 1700848, 1704061, 1712218, 1733148, 1744400, 1756959, 1766186, 1770297, 1774640, 1783782, 1790804, 1797186, 1819167, 1822095, 1835790, 1838687, 1840248, 1843265, 1858487, 1871701, 1874449, 1907155, 1933219, 1941873, 1953108, 1960964, 1970086, 1995385, 2005526, 2006388, 2012407, 2022419, 2027444, 2032071, 2046348, 2049691, 2081218, 2085045, 2107005, 2111011, 2117147, 2128804, 2130734, 2133565, 2163069, 2165643, 2183398, 2186582, 2200866, 2228833, 2238757, 2260397, 2287997, 2303690, 2306210, 2311079, 2319657, 2347177, 2348345, 2364629, 2380657, 2386691, 2392303, 2413369, 2429645, 2435861, 2445907, 2454603, 2461156, 2481207, 2493269, 2496558, 2526270, 2549274, 2559084, 2565601, 2571993, 2574622, 2589585, 2602736, 2606052, 2635578, 2636056, 2649712, 2667175, 2697913, 2705598, 2716472, 2726625, 2740640, 2748032, 2769317, 2773637, 2777175, 2796454, 2808141, 2818050, 2822209, 2828335, 2853048, 2858954, 2879003, 2898699, 2906226, 2928135, 2935468, 2950167, 2955230, 2959204, 2981209, 2999992, 3013106, 3016185, 3016728, 3033485, 3041287, 3046405, 3085842, 3097363, 3129048, 3137101, 3148974, 3153026, 3165425, 3172200, 3187649, 3208795, 3228028, 3239797, 3265353, 3281537, 3310390, 3330139, 3349916, 3351744, 3360950, 3366598, 3375910, 3382995, 3411775, 3438201, 3447140, 3453811, 3471520, 3485127, 3522748, 3569412, 3575690, 3578298, 3585562, 3593337, 3624737, 3626198, 3651501, 3667524, 3674434, 3675907, 3738616, 3754186, 3765841, 3786330, 3807381, 3818043, 3829535, 3831874, 3838373, 3862508, 3910613, 3942689, 3950184, 3954465, 3978469, 3992767, 4014701, 4032219, 4033924, 4065368, 4078004, 4089606, 4101646, 4119004, 4155098, 4166329, 4176904, 4182945, 4197748, 4211593, 4218728, 4253237, 4275441, 4288635, 4298689, 4301972, 4329866, 4357640, 4392330, 4403327, 4415543, 4434657, 4454780, 4460817, 4467239, 4489541, 4518764, 4526891, 4541320, 4560957, 4568090, 4582032, 4609341, 4631837, 4683082, 4688874, 4714962, 4728230, 4733954, 4744119, 4797763, 4819301, 4823437, 4850997, 4865482, 4886981, 4907820, 4931122, 4957782, 5005971, 5014678, 5031077, 5054902, 5059300, 5088659, 5119815, 5135680, 5153376, 5210102, 5213548, 5253584]
for _ in range(int(input())):
	n = int(input())
	sum = 0
	for i in range(n):
		print(lst[i], end=' ')
		sum += lst[i]
	print()
	print(sum)


from itertools import count, islice, chain
import time

def mian_chowla():
	mc = [1]
	yield mc[-1]
	psums = set([2])
	newsums = set([])
	for trial in count(2):
		for n in chain(mc, [trial]):
			sum = n + trial
			if sum in psums:
				newsums.clear()
				break
			newsums.add(sum)
		else:
			psums |= newsums
			newsums.clear()
			mc.append(trial)
			yield trial

def pretty(s, f):
	arr = []
	for n in islice(mian_chowla(), s, f):
		arr.append(int(n))
	return arr

def __starting_point():
	for _ in range(int(input())):
		n = int(input())
		lst = pretty(0, n)
		sum = 0
		for i in range(n):
			print(lst[i], end=' ')
			sum += lst[i]
		print()
		print(sum)
__starting_point()


from itertools import islice

def mianChowlas():
	mcs = [1]
	sumSet = set([2])
	x = 1
	while True:
		yield x
		(sumSet, mcs, x) = nextMC(sumSet, mcs, x)

def nextMC(setSums, mcs, n):

	def valid(x):
		for m in mcs:
			if x + m in setSums:
				return False
		return True
	x = until(valid)(succ)(n)
	setSums.update([x + y for y in mcs] + [2 * x])
	return (setSums, mcs + [x], x)

def main(t):
	genMianChowlas = mianChowlas()
	n = int(input())
	k = take(n)(genMianChowlas)
	print(*k)
	print(sum(k))
	if t > 1:
		main(t - 1)

def drop(n):

	def go(xs):
		if isinstance(xs, list):
			return xs[n:]
		else:
			take(n)(xs)
			return xs
	return lambda xs: go(xs)

def succ(x):
	return 1 + x

def take(n):
	return lambda xs: xs[0:n] if isinstance(xs, list) else list(islice(xs, n))

def until(p):

	def go(f, x):
		v = x
		while not p(v):
			v = f(v)
		return v
	return lambda f: lambda x: go(f, x)

def __starting_point():
	main(int(input()))
__starting_point()


try:
	from collections import Counter
	from sys import stdin, stdout

	def get_ints():
		return map(int, stdin.readline().strip().split())

	def get_list():
		return list(map(int, stdin.readline().strip().split()))

	def get_string():
		return stdin.readline().strip()

	def get_singleInt():
		return int(stdin.readline())

	def main():
		testCases = get_singleInt()
		a = reqNumbers()
		for i in range(testCases):
			limit = get_singleInt()
			for i in range(limit):
				print(a[i], end=' ')
			print()
			print(sum(a[:limit]))

	def reqNumbers():
		reqList = [1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851, 5123, 5243, 5298, 5751, 5998, 6374, 6801, 6925, 7460, 7547, 7789, 8220, 8503, 8730, 8942, 9882, 10200, 10587, 10898, 11289, 11614, 11876, 12034, 12931, 13394, 14047, 14534, 14901, 15166, 15688, 15972, 16619, 17355]
		return reqList

	def __starting_point():
		main()
except Exception:
	pass
__starting_point()


import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
input = sys.stdin.readline

def r():
	return int(input())

def rm():
	return map(int, input().split())

def rl():
	return list(map(int, input().split()))
for _ in range(r()):
	n = r()
	already = defaultdict(int)
	res = []
	sumi = 0
	i = 1
	len = 0
	while len != n:
		chk = True
		for j in res:
			if already[i + j] == 1:
				chk = False
				break
		if chk:
			for j in res:
				already[i + j] = 1
			already[i + i] = 1
			res.append(i)
			len += 1
		i += 1
	print(*res)
	print(sum(res))


t = int(input())
for i in range(t):
	n = int(input())
	j = 1
	a = 2
	ans = [1]
	sum1 = set([1, 2])
	while j < n:
		sum2 = set()
		for k in range(len(ans)):
			sum2.add(ans[k] + a)
		if len(sum2.intersection(sum1)) == 0:
			ans.append(a)
			sum1 = sum1.union(sum2)
			sum1.add(a * 2)
			j += 1
		else:
			a += 1
	for k in range(len(ans)):
		print(ans[k], end=' ')
	print()
	print(sum(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	total = 1
	coins = [1]
	sums = set([2])
	num = 2
	while len(coins) < n:
		notIn = True
		if 2 * num not in sums:
			sumx = set()
			for i in coins:
				if i + num not in sums:
					sumx.add(i + num)
				else:
					notIn = False
					break
			if notIn:
				sumx.add(2 * num)
				sums = sums.union(sumx)
				coins.append(num)
		num += 1
	for i in coins:
		print(i, end=' ')
	print('\n' + str(sum(coins)))


from array import *

def main():
	t = int(input())
	if 1 <= t <= 700:
		s = array('i', [])
		ql = array('i', [])
		for x in range(t):
			ql.append(int(input()))
		n = max(ql)
		if 1 <= n <= 700:
			l = array('i', [1])
			i = 2
			a = c = set()
			b = {2}
			while len(l) < n:
				if i - 1 in l:
					c = c.union(a.union(b))
				d = set()
				for j in l:
					d = d.union({i + j})
				if len(c.intersection({2 * i}.union(d))) == 0:
					b = d
					a = {2 * i}
					l.append(i)
				i = i + 1
			prev = 0
			for j in l:
				s.append(prev + j)
				prev = prev + j
			for j in ql:
				for i in range(j):
					print(l[i], end=' ')
				print()
				print(s[j - 1])
main()


temp = [1, 2, 4, 8]
data = [0] * 1000000
data[2] = 1
data[3] = 1
data[5] = 1
data[9] = 1
data[4] = 1
data[6] = 1
data[10] = 1
data[8] = 1
data[12] = 1
data[16] = 1
while len(temp) <= 100:
	for i in range(temp[len(temp) - 1], 2 * temp[len(temp) - 1] + 1):
		c = 0
		for j in range(0, len(temp)):
			if data[i + temp[j]] == 0:
				c += 1
		if c == len(temp):
			temp.append(i)
			for j in range(0, len(temp)):
				data[i + temp[j]] = 1
			break
for i in range(int(input())):
	n = int(input())
	print(*temp[0:n], sep=' ')
	print(sum(temp[0:n]))


ans = [0, 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851, 5123, 5243, 5298, 5751, 5998, 6374, 6801, 6925, 7460, 7547, 7789, 8220, 8503, 8730, 8942, 9882, 10200, 10587, 10898, 11289, 11614, 11876, 12034, 12931, 13394, 14047, 14534, 14901, 15166, 15688, 15972, 16619, 17355, 17932, 18845, 19071, 19631, 19670, 20722, 21948, 22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219, 28566, 29775, 30094, 31311, 32217, 32620, 32912, 34277, 35330, 35469, 36204, 38647, 39160, 39223, 39943, 40800, 41882, 42549, 43394, 44879, 45907, 47421, 47512, 48297, 50064, 50902, 52703, 52764, 54674, 55307, 56663, 58425, 59028, 60576, 60995, 62205, 63129, 64488, 66999, 67189, 68512, 68984, 70170, 71365, 75618, 76793, 77571, 79047, 80309, 83179, 84345, 87016, 87874, 88566, 89607, 91718, 92887, 93839, 95103, 97974, 99583, 101337, 102040, 103626, 104554, 106947, 107205, 108622, 111837, 112800, 113949, 114642, 116291, 117177, 121238, 125492, 126637, 129170, 130986, 131697, 134414, 134699, 136635, 139964, 143294, 144874, 146605, 147499, 148593, 150146, 152318, 152834, 156836, 157150, 160782, 163010, 163502, 164868, 170984, 172922, 174171, 177853, 180249, 182071, 185403, 188314, 190726, 190894, 193477, 196832, 199646, 201472, 202699, 205325, 206811, 208748, 214435, 217182, 218011, 225350, 226682, 229163, 231694, 233570, 234619, 235152, 238727, 240814, 247822, 253857, 254305, 260433, 261620, 262317, 266550, 269195, 271511, 274250, 274753, 280180, 284289, 290005, 293034, 295037, 296506, 298414, 302663, 305782, 308841, 317739, 321173, 323672, 324806, 329181, 331018, 336642, 340901, 343359, 347001, 348110, 348899, 362520, 366119, 368235, 370696, 371542, 377450, 380366, 382012, 382245, 384957, 387479, 390518, 391462, 399174, 403920, 411847, 412671, 416880, 417991, 422453, 433973, 434773, 440619, 441148, 443779, 446065, 456289, 458426, 462402, 470670, 474668, 475800, 481476, 482868, 498435, 501084, 508193, 511258, 514644, 524307, 527197, 535369, 536903, 538331, 542020, 555275, 564016, 566106, 567408, 572027, 582478, 583407, 585871, 593257, 596837, 598426, 599784, 607794, 610404, 621790, 624574, 627703, 633442, 640047, 648858, 659179, 663558, 667337, 672815, 673522, 686013, 691686, 693169, 694279, 696931, 703162, 711364, 723249, 729860, 731008, 739958, 740124, 744403, 753293, 768134, 770113, 773912, 779917, 787407, 794900, 797567, 800658, 813959, 814414, 827123, 829129, 839728, 847430, 850695, 851627, 862856, 880796, 884725, 889285, 896691, 897160, 904970, 909586, 915254, 922852, 935695, 937825, 938876, 959937, 961353, 964857, 970227, 976356, 980581, 986799, 1008106, 1009835, 1016906, 1020306, 1028612, 1033242, 1036012, 1042818, 1050881, 1051783, 1060844, 1086402, 1092043, 1096162, 1103456, 1123464, 1134057, 1136410, 1144080, 1145152, 1147774, 1156687, 1164278, 1166255, 1174751, 1187057, 1195316, 1201262, 1207345, 1212654, 1218610, 1225019, 1227887, 1240777, 1247071, 1258235, 1265462, 1274089, 1279515, 1288613, 1298980, 1306248, 1326918, 1333809, 1341190, 1343482, 1367480, 1372734, 1374779, 1384952, 1388147, 1394240, 1395346, 1409612, 1417336, 1418943, 1423296, 1446209, 1448494, 1462599, 1468933, 1474698, 1496110, 1502217, 1508335, 1513944, 1549693, 1552361, 1558304, 1567726, 1578307, 1593543, 1594370, 1596552, 1604567, 1611655, 1638201, 1657904, 1661549, 1668344, 1684653, 1700848, 1704061, 1712218, 1733148, 1744400, 1756959, 1766186, 1770297, 1774640, 1783782, 1790804, 1797186, 1819167, 1822095, 1835790, 1838687, 1840248, 1843265, 1858487, 1871701, 1874449, 1907155, 1933219, 1941873, 1953108, 1960964, 1970086, 1995385, 2005526, 2006388, 2012407, 2022419, 2027444, 2032071, 2046348, 2049691, 2081218, 2085045, 2107005, 2111011, 2117147, 2128804, 2130734, 2133565, 2163069, 2165643, 2183398, 2186582, 2200866, 2228833, 2238757, 2260397, 2287997, 2303690, 2306210, 2311079, 2319657, 2347177, 2348345, 2364629, 2380657, 2386691, 2392303, 2413369, 2429645, 2435861, 2445907, 2454603, 2461156, 2481207, 2493269, 2496558, 2526270, 2549274, 2559084, 2565601, 2571993, 2574622, 2589585, 2602736, 2606052, 2635578, 2636056, 2649712, 2667175, 2697913, 2705598, 2716472, 2726625, 2740640, 2748032, 2769317, 2773637, 2777175, 2796454, 2808141, 2818050, 2822209, 2828335, 2853048, 2858954, 2879003, 2898699, 2906226, 2928135, 2935468, 2950167, 2955230, 2959204, 2981209, 2999992, 3013106, 3016185, 3016728, 3033485, 3041287, 3046405, 3085842, 3097363, 3129048, 3137101, 3148974, 3153026, 3165425, 3172200, 3187649, 3208795, 3228028, 3239797, 3265353, 3281537, 3310390, 3330139, 3349916, 3351744, 3360950, 3366598, 3375910, 3382995, 3411775, 3438201, 3447140, 3453811, 3471520, 3485127, 3522748, 3569412, 3575690, 3578298, 3585562, 3593337, 3624737, 3626198, 3651501, 3667524, 3674434, 3675907, 3738616, 3754186, 3765841, 3786330, 3807381, 3818043, 3829535, 3831874, 3838373, 3862508, 3910613, 3942689, 3950184, 3954465, 3978469, 3992767, 4014701, 4032219, 4033924, 4065368, 4078004, 4089606, 4101646, 4119004, 4155098, 4166329, 4176904, 4182945, 4197748, 4211593, 4218728, 4253237, 4275441, 4288635, 4298689, 4301972, 4329866, 4357640, 4392330, 4403327, 4415543, 4434657, 4454780, 4460817, 4467239, 4489541, 4518764, 4526891, 4541320, 4560957, 4568090, 4582032, 4609341, 4631837, 4683082, 4688874, 4714962, 4728230, 4733954, 4744119, 4797763, 4819301, 4823437, 4850997, 4865482, 4886981, 4907820, 4931122, 4957782, 5005971, 5014678, 5031077, 5054902, 5059300, 5088659, 5119815, 5135680, 5153376, 5210102, 5213548, 5253584, 5256709]
anss = [0, 1, 3, 7, 15, 28, 49, 80, 125, 191, 272, 369, 492, 640, 822, 1026, 1278, 1568, 1929, 2330, 2805, 3370, 3963, 4625, 5400, 6222, 7138, 8108, 9124, 10283, 11595, 12990, 14513, 16085, 17906, 19802, 21831, 24085, 26464, 28974, 31754, 34679, 37834, 41188, 44779, 48576, 52574, 56871, 61304, 66083, 70934, 76057, 81300, 86598, 92349, 98347, 104721, 111522, 118447, 125907, 133454, 141243, 149463, 157966, 166696, 175638, 185520, 195720, 206307, 217205, 228494, 240108, 251984, 264018, 276949, 290343, 304390, 318924, 333825, 348991, 364679, 380651, 397270, 414625, 432557, 451402, 470473, 490104, 509774, 530496, 552444, 574970, 598261, 621825, 645706, 670302, 695070, 720701, 746738, 772993, 800212, 828778, 858553, 888647, 919958, 952175, 984795, 1017707, 1051984, 1087314, 1122783, 1158987, 1197634, 1236794, 1276017, 1315960, 1356760, 1398642, 1441191, 1484585, 1529464, 1575371, 1622792, 1670304, 1718601, 1768665, 1819567, 1872270, 1925034, 1979708, 2035015, 2091678, 2150103, 2209131, 2269707, 2330702, 2392907, 2456036, 2520524, 2587523, 2654712, 2723224, 2792208, 2862378, 2933743, 3009361, 3086154, 3163725, 3242772, 3323081, 3406260, 3490605, 3577621, 3665495, 3754061, 3843668, 3935386, 4028273, 4122112, 4217215, 4315189, 4414772, 4516109, 4618149, 4721775, 4826329, 4933276, 5040481, 5149103, 5260940, 5373740, 5487689, 5602331, 5718622, 5835799, 5957037, 6082529, 6209166, 6338336, 6469322, 6601019, 6735433, 6870132, 7006767, 7146731, 7290025, 7434899, 7581504, 7729003, 7877596, 8027742, 8180060, 8332894, 8489730, 8646880, 8807662, 8970672, 9134174, 9299042, 9470026, 9642948, 9817119, 9994972, 10175221, 10357292, 10542695, 10731009, 10921735, 11112629, 11306106, 11502938, 11702584, 11904056, 12106755, 12312080, 12518891, 12727639, 12942074, 13159256, 13377267, 13602617, 13829299, 14058462, 14290156, 14523726, 14758345, 14993497, 15232224, 15473038, 15720860, 15974717, 16229022, 16489455, 16751075, 17013392, 17279942, 17549137, 17820648, 18094898, 18369651, 18649831, 18934120, 19224125, 19517159, 19812196, 20108702, 20407116, 20709779, 21015561, 21324402, 21642141, 21963314, 22286986, 22611792, 22940973, 23271991, 23608633, 23949534, 24292893, 24639894, 24988004, 25336903, 25699423, 26065542, 26433777, 26804473, 27176015, 27553465, 27933831, 28315843, 28698088, 29083045, 29470524, 29861042, 30252504, 30651678, 31055598, 31467445, 31880116, 32296996, 32714987, 33137440, 33571413, 34006186, 34446805, 34887953, 35331732, 35777797, 36234086, 36692512, 37154914, 37625584, 38100252, 38576052, 39057528, 39540396, 40038831, 40539915, 41048108, 41559366, 42074010, 42598317, 43125514, 43660883, 44197786, 44736117, 45278137, 45833412, 46397428, 46963534, 47530942, 48102969, 48685447, 49268854, 49854725, 50447982, 51044819, 51643245, 52243029, 52850823, 53461227, 54083017, 54707591, 55335294, 55968736, 56608783, 57257641, 57916820, 58580378, 59247715, 59920530, 60594052, 61280065, 61971751, 62664920, 63359199, 64056130, 64759292, 65470656, 66193905, 66923765, 67654773, 68394731, 69134855, 69879258, 70632551, 71400685, 72170798, 72944710, 73724627, 74512034, 75306934, 76104501, 76905159, 77719118, 78533532, 79360655, 80189784, 81029512, 81876942, 82727637, 83579264, 84442120, 85322916, 86207641, 87096926, 87993617, 88890777, 89795747, 90705333, 91620587, 92543439, 93479134, 94416959, 95355835, 96315772, 97277125, 98241982, 99212209, 100188565, 101169146, 102155945, 103164051, 104173886, 105190792, 106211098, 107239710, 108272952, 109308964, 110351782, 111402663, 112454446, 113515290, 114601692, 115693735, 116789897, 117893353, 119016817, 120150874, 121287284, 122431364, 123576516, 124724290, 125880977, 127045255, 128211510, 129386261, 130573318, 131768634, 132969896, 134177241, 135389895, 136608505, 137833524, 139061411, 140302188, 141549259, 142807494, 144072956, 145347045, 146626560, 147915173, 149214153, 150520401, 151847319, 153181128, 154522318, 155865800, 157233280, 158606014, 159980793, 161365745, 162753892, 164148132, 165543478, 166953090, 168370426, 169789369, 171212665, 172658874, 174107368, 175569967, 177038900, 178513598, 180009708, 181511925, 183020260, 184534204, 186083897, 187636258, 189194562, 190762288, 192340595, 193934138, 195528508, 197125060, 198729627, 200341282, 201979483, 203637387, 205298936, 206967280, 208651933, 210352781, 212056842, 213769060, 215502208, 217246608, 219003567, 220769753, 222540050, 224314690, 226098472, 227889276, 229686462, 231505629, 233327724, 235163514, 237002201, 238842449, 240685714, 242544201, 244415902, 246290351, 248197506, 250130725, 252072598, 254025706, 255986670, 257956756, 259952141, 261957667, 263964055, 265976462, 267998881, 270026325, 272058396, 274104744, 276154435, 278235653, 280320698, 282427703, 284538714, 286655861, 288784665, 290915399, 293048964, 295212033, 297377676, 299561074, 301747656, 303948522, 306177355, 308416112, 310676509, 312964506, 315268196, 317574406, 319885485, 322205142, 324552319, 326900664, 329265293, 331645950, 334032641, 336424944, 338838313, 341267958, 343703819, 346149726, 348604329, 351065485, 353546692, 356039961, 358536519, 361062789, 363612063, 366171147, 368736748, 371308741, 373883363, 376472948, 379075684, 381681736, 384317314, 386953370, 389603082, 392270257, 394968170, 397673768, 400390240, 403116865, 405857505, 408605537, 411374854, 414148491, 416925666, 419722120, 422530261, 425348311, 428170520, 430998855, 433851903, 436710857, 439589860, 442488559, 445394785, 448322920, 451258388, 454208555, 457163785, 460122989, 463104198, 466104190, 469117296, 472133481, 475150209, 478183694, 481224981, 484271386, 487357228, 490454591, 493583639, 496720740, 499869714, 503022740, 506188165, 509360365, 512548014, 515756809, 518984837, 522224634, 525489987, 528771524, 532081914, 535412053, 538761969, 542113713, 545474663, 548841261, 552217171, 555600166, 559011941, 562450142, 565897282, 569351093, 572822613, 576307740, 579830488, 583399900, 586975590, 590553888, 594139450, 597732787, 601357524, 604983722, 608635223, 612302747, 615977181, 619653088, 623391704, 627145890, 630911731, 634698061, 638505442, 642323485, 646153020, 649984894, 653823267, 657685775, 661596388, 665539077, 669489261, 673443726, 677422195, 681414962, 685429663, 689461882, 693495806, 697561174, 701639178, 705728784, 709830430, 713949434, 718104532, 722270861, 726447765, 730630710, 734828458, 739040051, 743258779, 747512016, 751787457, 756076092, 760374781, 764676753, 769006619, 773364259, 777756589, 782159916, 786575459, 791010116, 795464896, 799925713, 804392952, 808882493, 813401257, 817928148, 822469468, 827030425, 831598515, 836180547, 840789888, 845421725, 850104807, 854793681, 859508643, 864236873, 868970827, 873714946, 878512709, 883332010, 888155447, 893006444, 897871926, 902758907, 907666727, 912597849, 917555631, 922561602, 927576280, 932607357, 937662259, 942721559, 947810218, 952930033, 958065713, 963219089, 968429191, 973642739, 978896323, 984153032]
t = int(input())
for _ in range(0, t):
	n = int(input())
	print(*ans[1:n + 1])
	print(anss[n])


l = [1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851, 5123, 5243, 5298, 5751, 5998, 6374, 6801, 6925, 7460, 7547, 7789, 8220, 8503, 8730, 8942, 9882, 10200, 10587, 10898, 11289, 11614, 11876, 12034, 12931, 13394, 14047, 14534, 14901, 15166, 15688]
try:
	for _ in range(int(input())):
		n = int(input())
		print(*l[:n])
		print(sum(l[:n]))
except:
	pass