Good Partition

We say that a positive integer ( n ) is good if there exists an ordered ( n )-tuple of integers ( (a_1,a_2,\dots,a_n) ) satisfying [ \sum_{i=1}^n a_i = n \quad\text{and}\quad \prod_{i=1}^n a_i = n. ] In other words, the sum and the product of the ( n ) numbers are both equal to ( n ). If ( n ) is good then such a tuple is called a good partition of ( n ).

For each test case you are given an integer ( n ). If ( n ) is good, print any one good partition (the ( n ) numbers separated by spaces). If no good partition exists for ( n ) print -1.

Note: A solution (if it exists) can be constructed in the following way. For ( n>1 ) we try to choose two special numbers ( A ) and ( B ) and then fill the remaining ( n-2 ) places with copies of 1 or ( -1 ) so that the overall conditions

[ A + B + \underbrace{(\mbox{sum of some copies of }-1)}{\text{say } m \mbox{ copies}} + \underbrace{(\mbox{rest ones})}{n-2-m}\ = n, \quad A\cdot B\cdot (-1)^m = \begin{cases} n, & \mbox{if } m \mbox{ is even}, \ -n, & \mbox{if } m \mbox{ is odd}. \end{cases} ] A little algebra shows that these conditions become

[ A+B = 2+2m \quad\text{and}\quad A\cdot B = \begin{cases} n & (m\mbox{ even}),\ -n & (m\mbox{ odd}). \end{cases} ]

Then one may try various values of ( m ) (with ( 0\le m \le n-2 )) so that the quadratic equation in ( x ):

[ x^2 - (2+2m)x + \Bigl(\pm n\Bigr)=0 \quad (+n \mbox{ if } m \mbox{ is even, } -n \mbox{ if } m \mbox{ is odd}) ]

has integer roots. (Also note that for ( n=1 ) the only partition is ( [1] ).)

It turns out that not all ( n ) are good. For example, one may verify that ( n=2,3,4,6,7 ) do not have any good partition, while ( n=5,8,9,12,\dots ) are good.

Your task is to decide for each given ( n ) whether it is good, and if so, output any one good partition.

inputFormat

The first line contains an integer ( T ) (the number of test cases). Each of the next ( T ) lines contains one integer ( n ).

outputFormat

For each test case, if ( n ) is good then output a line with ( n ) space–separated integers forming a good partition (i.e. their sum and product are both ( n )). Otherwise, output a line with -1.

sample

5
1
2
5
6
8

1
-1
5 -1 -1 1 1
-1
4 2 -1 -1 1 1 1 1