Description

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Their description follows.

Each test case contains one line with a single integer $n$ ($2 \le n \le 10^9$) — the required final number of candies.

Output

For each test case, output the following.

If it's possible to eventually have $n$ candies within $40$ spells, in the first line print an integer $m$ ($1 \le m \le 40$), representing the total number of spells you use.

In the second print $m$ integers $a_{1}, a_{2}, \ldots, a_{m}$ ($a_{i}$ is $1$ or $2$) separated by spaces, where $a_{i} = 1$ means that you use the first spell in the $i$-th step, while $a_{i} = 2$ means that you use the second spell in the $i$-th step.

Note that you do not have to minimize $m$, and if there are multiple solutions, you may output any one of them.

If it's impossible, output $-1$ in one line.

4
2
3
7
17
 
 

-1
1
2 
2
2 2 
4
2 1 1 1

Note

For $n=3$, you can just use the second spell once, and then have $2 \cdot 1 + 1 = 3$ candies.

For $n=7$, you can use the second spell twice. After the first step, you will have $3$ candies. And after the second step, you will have $2 \cdot 3 + 1 = 7$ candies.