SUM Equals LCM

border Amra shobai Raja
Limits 1s, 512 MB

Given NN, print a sequence of NN positive integers A1,A2,,ANA_1, A_2, \ldots, A_N that satisfy the following conditions:

  • i=1NAi=lcm(A1,A2,,AN)\sum_{i=1}^{N}A_i = \text{lcm}(A_1, A_2, \ldots, A_N)
  • 1Ai1091 \leq A_i \leq 10^9

If there exists no such sequence, print 1-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(1T100)T(1 \leq T \leq 100)— the number of test cases.

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

Sum of NN over all test cases does not exceed 10610^6.

Output

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

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

Sample

InputOutput
3
1
2
4
1
-1
2 3 3 4

Submit

Login to submit.

Statistics

94% Solution Ratio
AlfehsaniEarliest, 1M ago
MOHIR_MBSTUFastest, 0.0s
JIANEELightest, 5.5 kB
OvicorshoShortest, 255B
Toph uses cookies. By continuing you agree to our Cookie Policy.