K. Kakalan's Karma
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Let's recall the problem B in NTUIM PDAO 2017:

———————————————————————–

Kakalan will enter the National Taiwan Elementary School (NTES), in which there are $$$k$$$ grades, this year. In this school, students in the $$$i$$$-th $$$(1 \leq i \lt k)$$$ grade are required to pass an upgrade exam to advance to the next grade (i.e. the $$$(i + 1)$$$-th grade) at the end of the year. Likewise, students in the $$$k$$$-th grade are also required to pass a graduation exam to receive the diploma from NTES. However, students in the $$$i$$$-th $$$(1 \leq i \leq k)$$$ grade would be demoted to the $$$a_i$$$-th $$$(1 \leq a_i \leq i)$$$ grade if failing the upgrade exam.

Kakalan is good at cheating in the exam – if he fails the upgrade exam in the $$$i$$$-th grade, he is bound to pass it (the upgrade exam in the $$$i$$$-th grade) the next time. However, if he passes the upgrade exam in the $$$i$$$-th grade, he may pass or fail it (the upgrade exam in the $$$i$$$-th grade) should he take the same exam again. At most how many years will Kakalan take to study if he would like to graduate from NTES; that is, to pass the graduation exam successfully?

———————————————————————–

Nevertheless, Karma is a b*tch. Knowing the opportunistic student, Kakalan, is planning on cheating, his IM (interesting math) teacher decides to customize a school system for Kakalan. After informing the principal of NTES, he intends to keep Kakalan from being graduated for exactly $$$n$$$ years if Kakalan performs his aforementioned cheating skill, but takes the longest time to graduate. His IM teacher wants you to find whether it is possible to build such a school system within $$$2000$$$ grades, as school resources are limited. If so, come up with any possible solution satisfying the constraints. Note that you do not have to minimize the number of grades.

Input

The first line contains one integer $$$t\,(1 \leq t \leq 100)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

The only line of each test case contains one integer $$$n \, (1 \leq n \leq 10^{18})$$$, the number of years for which the IM teacher intends to keep Kakalan from being graduated if Kakalan performs his aforementioned cheating skill, but takes the longest time to graduate.

Output

For each test case, print -1 if it is impossible for the IM teacher to construct such a school system within $$$2000$$$ grades.

Otherwise, print $$$2$$$ lines. You have to come up with any possible school system $$$k$$$ and $$$\left\langle a_i \right\rangle_{i = 1}^{k}$$$ for Kakalan's IM teacher. The first line should contain a single integer $$$k\,(1 \leq k \leq 2000)$$$ — the number of grades. The second line should contain $$$k$$$ integers, $$$a_1, a_2, \ldots, a_k\,(1 \leq a_i \leq i)$$$, where students in the $$$i$$$-th grade failing the upgrade exam are demoted to $$$a_i$$$-th grade.

Example
Input
4
62
1
2
16
Output
5
1 1 1 1 1
-1
1
1
4
1 1 1 4
Note

Intuitively speaking, this problem is similar to the "inverse version" of the problem B in NTUIM PDAO 2017.

In the first test case, this is the inverse version of the sample test case in the problem B in NTUIM PDAO 2017. Kakalan needs $$$62$$$ years to graduate from NTES with the school system $$$\left\langle a_i \right\rangle_{i = 1}^{5} = \left\langle 1, 1, 1, 1, 1 \right\rangle$$$.

In the second test case, it can be proven that there does not exist any possible school system such that Kakalan can graduate in one year if he performs his aforementioned cheating skill, but takes the longest time to graduate.