Candies
Description
This problem is about candy. Initially, you only have $1$ candy, and you want to have exactly $n$ candies.
You can use the two following spells in any order at most $40$ times in total.
- Assume you have $x$ candies now. If you use the first spell, then $x$ candies become $2x-1$ candies.
- Assume you have $x$ candies now. If you use the second spell, then $x$ candies become $2x+1$ candies.
Construct a sequence of spells, such that after using them in order, you will have exactly $n$ candies, or determine it's impossible.
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.
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.
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.