Given a positive integer $n$.

We define $\Omega(S)$ as the set of all subset sums of non-empty subsets of a set $S$.

Formally, $\Omega(S)=\{x\mid x=\sum\limits_{i\in T}i,T\subseteq S,T\neq \varnothing\}$.

For example, when $S=\{2,0,-3,5\}$, $\Omega(S)=\{-3,-1,0,2,4,5,7\}$.

You need to construct a set $S$ of size $n$ such that:

• All elements in set $S$ are integers between $-10^9$ and $10^9$ inclusive;
• $|\Omega(S)|$ is minimized, i.e., the number of elements in $\Omega(S)$ is as small as possible.

Input

This problem contains multiple test cases.

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

Each test case follows. For each test case, input a single line containing a positive integer $n$.

Output

For each test case, output a single line containing $n$ integers, representing all elements of the constructed set $S$.

Any output that satisfies the requirements will be accepted.

Examples

Input 1

3
1
2
4

Output 1

3
0 5
2 0 -2 4

Note

For the first test case, $S=\{3\}$, $\Omega(S)=\{3\}$. Of course, $\{0\}$, $\{-2\}$, etc., are also valid sets $S$.

For the second test case, $S=\{0,5\}$, $\Omega(S)=\{0,5\}$.

For the third test case, $S=\{2,0,-2,4\}$, $\Omega(S)=\{-2,0,2,4,6\}$.

It can be proven that the above constructions satisfy the conditions.

Constraints

Let $\sum n$ denote the sum of $n$ over a single test case.

For all data, $1 \le T \le 100$, $1 \le n \le 10^6$, $\sum n \le 10^6$.