Binary Colouring
Description
You are given a positive integer $x$. Find any array of integers $a_0, a_1, \ldots, a_{n-1}$ for which the following holds:
- $1 \le n \le 32$,
- $a_i$ is $1$, $0$, or $-1$ for all $0 \le i \le n - 1$,
- $x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$,
- There does not exist an index $0 \le i \le n - 2$ such that both $a_{i} \neq 0$ and $a_{i + 1} \neq 0$.
It can be proven that under the constraints of the problem, a valid array always exists.
Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The only line of each test case contains a single positive integer $x$ ($1 \le x < 2^{30}$).
For each test case, output two lines.
On the first line, output an integer $n$ ($1 \le n \le 32$) — the length of the array $a_0, a_1, \ldots, a_{n-1}$.
On the second line, output the array $a_0, a_1, \ldots, a_{n-1}$.
If there are multiple valid arrays, you can output any of them.
Input
Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The only line of each test case contains a single positive integer $x$ ($1 \le x < 2^{30}$).
Output
For each test case, output two lines.
On the first line, output an integer $n$ ($1 \le n \le 32$) — the length of the array $a_0, a_1, \ldots, a_{n-1}$.
On the second line, output the array $a_0, a_1, \ldots, a_{n-1}$.
If there are multiple valid arrays, you can output any of them.
7
1
14
24
15
27
11
19
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
Note
In the first test case, one valid array is $[1]$, since $(1) \cdot 2^0 = 1$.
In the second test case, one possible valid array is $[0,-1,0,0,1]$, since $(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$.