题目描述

起初，你只有 $1$ 颗糖，而你想要恰好 $n$ 颗糖。

你可以念以下两种咒语，但你所念的咒语的总数不能超过 $40$ 句：

• 假设你现在有 $x$ 颗糖。如果你念咒语一，那么你的 $x$ 颗糖就变成了 $2x - 1$ 颗糖。
• 假设你现在有 $x$ 颗糖。如果你念咒语二，那么你的 $x$ 颗糖就变成了 $2x + 1$ 颗糖。

如果可以念不超过 $40$ 句咒语就能获得恰好 $n$ 颗糖，则你需要构造一个可能的咒语序列，否则你应判断这样的咒语序列不存在。

输入格式

每个测试点包含多组测试数据。每组测试数据的第一行包含一个整数 $t \text{ } (1 \le t \le 10 ^ 4)$，代表测试数据组数。

每组测试数据只有一行，该行包含一个整数 $n \text{ } (2 \le n \le 10 ^ 9)$，代表你需要获得恰好 $n$ 颗糖。

输出格式

对于每组测试数据，输出以下内容。

如果可以念不超过 $40$ 句咒语就能获得恰好 $n$ 颗糖，那么在第一行输出一个整数 $m$，代表你所念的咒语的总数。

在第二行输出 $m$ 个由空格隔开的整数 $a_1, a_2,..., a_m$ $(a_i = 1 \text{ or } a_i = 2)$，其中 $a_i = 1$ 代表你的第 $i$ 句咒语是咒语一，$a_i = 2$ 代表你的第 $i$ 句咒语是咒语二。

注意，你的答案不需要使得 $m$ 最小，如果有多种可能的答案，输出任意一种即可。

如果不可能获得恰好 $n$ 颗糖，在该行单独输出 $-1$。

说明/提示

对于 $n = 3$，你只需要念一句咒语二，你就有了 $2 \times 1 + 1 = 3$ 颗糖。

对于 $n = 7$，你只需要念两句咒语二。第一步后，你就有了 $3$ 颗糖。而第二步后，你就有了 $2 \times 3 + 1 = 7$ 颗糖。

样例

4
2
3
7
17

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