Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^6$) — the length of the sequence $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output $n$ integers $a_1, a_2, \ldots, a_n$ — the elements of the sequence $a$.

If there are multiple answers, print any of them.

3
2
3
4
 
 

114514 114514
1 2 2
3 3 4 4

Note

In the third test case, $a = [3, 4, 2, 6]$ violates the second condition since $a_1 \cdot a_2 = a_3 \cdot a_4$. $a = [2, 3, 4, 4]$ satisfy the conditions but its number of distinct elements isn't minimum.