# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

*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}$.*

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})$`

.

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).

Input | Output |
---|---|

2 6 20 | 5 4 2 3 2 5 -1 |

In the first test case, For the sequence
So the multiset |

83% Solution Ratio

Shahwat_Has9Earliest,

Shahwat_Has9Fastest, 0.0s

Shahwat_Has9Lightest, 0 B

steinumShortest, 254B

Login to submit

Hint: Let $k$ be the LIS of the whole sequence. Then, the LCM of all subarray LIS-s is exactly equal...