Given an integer N, construct an array A of length N such that:
1 ≤ A_{i} ≤ 10^{18} for all (1 ≤ i ≤ N);
There exists a [subsequence] of length greater than 1 such that the [gcd] of all elements of the subsequence is i, for all 1 ≤ i ≤ N.  
More formally, for all (1 ≤ i ≤ N), there exists a subsequence S of array A such that the length of the subsequence is k (2 ≤ k ≤ N) and gcd(S_{1},S_{2},\ldots,S_{k})=i.  

It can be proven that it is always possible to construct such A under given constraints. If there exist multiple such arrays, print any. 

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow.
- The only line of each test case contains an integer N - the length of the array to be constructed.

------ Output Format ------ 

For each test case, output a single line containing N space-separated integers, denoting the elements of the array A. The i^{th} of these N integers is the i^{th} element of the array A. 

If there exist multiple such arrays, print any.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$3 ≤ N ≤ 10^{3}$
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{3}$.

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

----- Sample Output 1 ------ 
2 3 6
4 24 10 15
----- explanation 1 ------ 
Test case $1$: A possible array satisfying all the conditions is [2, 3, 6]:
- For $i=1$: Choose $S = [A_{1}, A_{2}, A_{3}] = [2, 3, 6]$. Thus, $gcd(2,3,6)=1$.
- For $i=2$: Choose $S = [A_{1}, A_{3}] = [2, 6]$. Thus, $gcd(2,6)=2$.
- For $i=3$: Choose $S = [A_{2}, A_{3}] = [3, 6]$. Thus, $gcd(3,6)=3$.

Test case $2$: A possible array satisfying all the conditions is [4, 24, 10, 15]:
- For $i=1$: Choose $S = [4, 24, 10, 15]$. Thus, $gcd(4,24,10,15)=1$.
- For $i=2$: Choose $S = [24, 10]$. Thus, $gcd(24,10)=2$.
- For $i=3$: Choose $S = [24, 15]$. Thus, $gcd(24,15)=3$.
- For $i=4$: Choose $S = [4, 24]$. Thus, $gcd(4,24)=4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc


Solutions:
from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		if n == 3:
			print(2, 3, 6)
			continue
		if n == 4:
			print(4, 10, 15, 24)
			continue
		ans = []
		p = 1
		c = 0
		for j in range(3, n + 1):
			if c < 5:
				ans.append(j)
				p *= j
				c += 1
			else:
				ans.append(p)
				ans.append(j)
				c = 1
				p = j
		if p != n:
			ans.append(p)
		ans.append(2 * n)
		if len(ans) > n:
			print(*ans[len(ans) - n:])
		elif len(ans) == n:
			print(*ans)
		else:
			ans.append(2)
			print(*ans)
main()