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 $[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,$ 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$. |

83% Solution Ratio

Shahwat_Has9Earliest,

Shahwat_Has9Fastest, 0.0s

Shahwat_Has9Lightest, 0 B

steinumShortest, 254B

Login to submit

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

Toph uses cookies. By continuing you agree to our Cookie Policy.