Given $K$, you need to construct a sequence $(A_i)_{i=1}^n$ of length $n$ such that:

1. $A_i$ are integers between $-10^{16}$ and $10^{16}$.
2. There are exactly $K$ subsets $S$ of $\{1, 2, \dots, n\}$ such that $\sum_{i \in S} A_i = 0$ (including the empty set).
3. $n$ is an integer between $0$ and $30$.

Input

The input contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains an integer $K$, the query parameter.

Output

For each test case, output two lines. The first line contains an integer $n$, the length of the sequence. The second line contains $n$ integers representing the sequence.

Examples

Input 1

2
3
16

Output 1

5
2021 -1000 -1021 -2000 -21
4
0 0 0 0

Subtasks

For all test cases, it is guaranteed that $1 \leq T \leq 1000$ and $1 \leq K \leq 10^6$.