Isn't It Strange?

Limits 1s, 512 MB · Custom Checker

Cherry isn't feeling well right now as she found a problem that she couldn't solve. So she started to listen to Isn't It Strange? and you, to make her happy, have to solve the problem for her.

You are given an integer $L$ . You have to find an integer sequence $a_1, a_2, \ldots, a_n$ such that the following conditions are satisfied:

The length of the array, $n$ , is positive and doesn't exceed $1000$ .
For each valid $i$ , $1 \le a_i \le 1000$ .
Consider a multiset $S$ which contains $\frac{n * (n + 1)}{2}$ integers: for each $1 \le l \le r \le n$ , $LIS(l, \, r)$ belongs to $S$ . Then, the LCM of the elements of $S$ is exactly equal to $L$ .

Here, $LIS(l, r)$ is the length of the longest increasing subsequence of the sequence $a_l, a_{l + 1}, \ldots, a_r$ .

The longest increasing subsequence of a sequence $b_1, b_2, \ldots, b_m$ is the longest sequence of valid indices $i_1, i_2, \ldots, i_k$ such that $i_1 \lt i_2 \lt \ldots \lt i_k$ and $b_{i_1} \lt b_{i_2} \lt \ldots \lt b_{i_k}$ .

Input

The first line of the input contains a single integer $t(1 \le t \le 100)$ denoting the number of test cases. The description of $t$ test cases follows.

The first and only line of each test case contains an integer $L(1 \le L \le 10^{18})$ .

Output

For each test case, print the answer in the following way:

If a solution exists, then on the first line print $n$ . On the next line, print $n$ space-separated integers $a_1, a_2, \ldots, a_n$ .
If there are multiple solutions, you can print any.
If there is no solution, then just output "-1" (without quotes).

Sample

Input Output

Input	Output
2 6 20	5 4 2 3 2 5 -1
In the first test case, For the sequence $[4, 2, 3, 2, 5]$ , $LIS(1, 1) = 1 , \, LIS(2, 2) = 1, \, LIS(3, 3) = 1, \, LIS(4, 4) = 1, \, LIS(5, 5) = 1,$ $LIS(1, 2) = 1, \, LIS(2, 3) = 2, \, LIS(3, 4) = 1, \, LIS(4, 5) = 2,$ $LIS(1, 3) = 2, \, LIS(2, 4) = 2, \, LIS(3, 5) = 2,$ $LIS(1, 4) = 2, \, LIS(2, 5) = 3,$ $LIS(1, 5) = 3$ . So the multiset $S = \{1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3\}$ . And the LCM of the elements of $S$ is exactly equal to $6$ .

2
6
20

5
4 2 3 2 5
-1

In the first test case,

For the sequence $[4, 2, 3, 2, 5]$ ,

$LIS(1, 1) = 1 , \, LIS(2, 2) = 1, \, LIS(3, 3) = 1, \, LIS(4, 4) = 1, \, LIS(5, 5) = 1,$
$LIS(1, 2) = 1, \, LIS(2, 3) = 2, \, LIS(3, 4) = 1, \, LIS(4, 5) = 2,$
$LIS(1, 3) = 2, \, LIS(2, 4) = 2, \, LIS(3, 5) = 2,$
$LIS(1, 4) = 2, \, LIS(2, 5) = 3,$
$LIS(1, 5) = 3$ .

So the multiset $S = \{1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3\}$ . And the LCM of the elements of $S$ is exactly equal to $6$ .