Practice on Toph

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

Isn't It Strange?

By YouKnowWho · 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 LL. You have to find an integer sequence a1,a2,,ana_1, a_2, \ldots, a_n such that the following conditions are satisfied:

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

Here, LIS(l,r)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 b1,b2,,bmb_1, b_2, \ldots, b_m is the longest sequence of valid indices i1,i2,,iki_1, i_2, \ldots, i_k such that i1<i2<<iki_1 \lt i_2 \lt \ldots \lt i_k and bi1<bi2<<bikb_{i_1} \lt b_{i_2} \lt \ldots \lt b_{i_k}.

Input

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

The first and only line of each test case contains an integer L(1L1018)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 nn. On the next line, print nn space-separated integers a1,a2,,ana_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

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

In the first test case,

For the sequence [4,2,3,2,5][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, 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, 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, 3) = 2, \, LIS(2, 4) = 2, \, LIS(3, 5) = 2,
LIS(1,4)=2,LIS(2,5)=3,LIS(1, 4) = 2, \, LIS(2, 5) = 3,
LIS(1,5)=3LIS(1, 5) = 3.

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


    Discussion

    Statistics


    83% Solution Ratio

    Shahwat_Has9Earliest, 9M ago

    Shahwat_Has9Fastest, 0.0s

    Shahwat_Has9Lightest, 0 B

    steinumShortest, 254B

    Submit

    Login to submit

    Editorial

    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.