SUM Equals LCM

Given $N$, print a sequence of $N$ positive integers $A_1, A_2, \ldots, A_N$ that satisfy the following conditions:

• $\sum_{i=1}^{N}A_i = \text{lcm}(A_1, A_2, \ldots, A_N)$
• $1 \leq A_i \leq 10^9$

If there exists no such sequence, print $-1$.

• lcm denotes the least common multiple. The least common multiple of some positive integers is the least positive integer which is multiple for each of them.

Input

The first line of each test case contains an integer $T(1 \leq T \leq 100)$— the number of test cases.

Each of the next $T$ lines will contain an integer $N(1 \leq N \leq 10^5)$— the length of the sequence.

Sum of $N$ over all test cases does not exceed $10^6$.

Output

For each test case, print $N$ space separated positive integers that satisfy the given conditions on a separate line. If there exists no such sequence, print $-1$.

If there are multiple sequences that satisfy the conditions, you can output any of them.

Sample

Input	Output
3 1 2 4	1 -1 2 3 3 4