K. K-onstruction
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given an integer $$$K$$$ such that $$$1 \le K \le 10^6$$$. Construct any array $$$A$$$ of numbers for which the following properties hold:

  • The size of $$$A$$$ is between $$$1$$$ and $$$30$$$;
  • All elements are integers between $$$-10^{16}$$$ and $$$10^{16}$$$;
  • Let $$$N$$$ be the size of $$$A$$$. Then there are exactly $$$K$$$ subsets $$$S$$$ (possibly empty) of set $$$\{1, 2, \ldots, N\}$$$ for which $$$\sum_{i \in S} A_i = 0$$$.

It can be shown that, under the constraints above, such array $$$A$$$ always exists.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases.

Each of the next $$$t$$$ lines contains a single integer $$$K$$$ ($$$1 \le K \le 10^6$$$).

Output

For each test case, on the first line, output a single integer $$$N$$$ ($$$1 \le N \le 30$$$), the size of your array.

On the second line, output $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$-10^{16} \le A_i \le 10^{16}$$$), the elements of the array.

Example
Input
2
3
16
Output
5
2021 -1000 -1021 -2000 -21
4
0 0 0 0
Note

Note that the elements of the array don't have to be distinct.