CF1810B.Candies

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.

这个问题关于糖果。初始时，你只有 $1$ 颗糖果，而你的目标是恰好拥有 $n$ 颗糖果。

你可以按任意顺序使用以下两种法术，总共至多使用 $40$ 次。

• 假设你现在有 $x$ 颗糖果。若使用第一种法术，则 $x$ 颗糖果变为 $2x-1$ 颗糖果。
• 假设你现在有 $x$ 颗糖果。若使用第二种法术，则 $x$ 颗糖果变为 $2x+1$ 颗糖果。

请构造一个法术序列，使得按该顺序使用后，你恰好拥有 $n$ 颗糖果；或者判断这是不可能的。

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.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是这些测试用例的描述。

每个测试用例包含一行，其中有一个整数 $n$（$2 \le n \le 10^9$），表示所需的最终糖果数量。

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.

对于每个测试用例，输出如下内容：

如果能在至多 $40$ 次法术内最终恰好获得 $n$ 颗糖果，则在第一行输出一个整数 $m$（$1 \le m \le 40$），表示你所使用的法术总次数。

在第二行输出 $m$ 个整数 $a_{1}, a_{2}, \ldots, a_{m}$（每个 $a_{i}$ 为 $1$ 或 $2$），以空格分隔；其中 $a_{i} = 1$ 表示在第 $i$ 步使用第一个法术，而 $a_{i} = 2$ 表示在第 $i$ 步使用第二个法术。

注意：你无需最小化 $m$；若存在多种解，输出任意一种即可。

如果不可能实现，则在一行中输出 $-1$。

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.

当 $n=3$ 时，只需使用一次第二种法术，即可得到 $2 \cdot 1 + 1 = 3$ 颗糖果。

当 $n=7$ 时，可以使用两次第二种法术。第一次操作后，你将拥有 $3$ 颗糖果；第二次操作后，你将拥有 $2 \cdot 3 + 1 = 7$ 颗糖果。