给你一个正整数 $$$x$$$。查找满足以下条件的任意整数数组 $$$a_0, a_1, \ldots, a_{n-1}$$$:
- $$$1 \le n \le 32$$$,
- $$$a_i$$$ 是 $$$1$$$、$$$0$$$ 或 $$$-1$$$ 对于所有 $$$0 \le i \le n - 1$$$,
- $$$x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$$$,
- 不存在索引 $$$0 \le i \le n - 2$$$ 使得 $$$a_{i} \neq 0$$$ 和 $$$a_{i + 1} \neq 0$$$ 都成立。
可以证明,在问题的约束下,有效的数组总是存在的。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个正整数 $$$x$$$ ($$$1 \le x < 2^{30}$$$)。
输出
对于每个测试用例,输出两行。
在第一行,输出一个整数 $$$n$$$ ($$$1 \le n \le 32$$$) — 数组 $$$a_0, a_1, \ldots, a_{n-1}$$$ 的长度。
在第二行,输出数组$$$a_0, a_1, \ldots, a_{n-1}$$$。
如果有多个有效数组,则可以输出其中任何一个。
示例
输入 #1
7 1 14 24 15 27 11 19
输出 #1
1 1 5 0 -1 0 0 1 6 0 0 0 -1 0 1 5 -1 0 0 0 1 6 -1 0 -1 0 0 1 5 -1 0 -1 0 1 5 -1 0 1 0 1
注意
在第一个测试用例中,一个有效数组是 $$$[1]$$$,因为 $$$(1) \cdot 2^0 = 1$$$。
在第二个测试用例中,一个可能的有效数组是 $$$[0,-1,0,0,1]$$$,因为 $$$(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$$$。