No submission language available for this problem.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The only line for each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of pillars for the construction of the roof.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case print $n$ integers $p_1$, $p_2$, $\ldots$, $p_n$ — the sequence of pillar heights with the smallest construction cost.

If there are multiple answers, print any of them.

Samples

4
2
3
5
10

0 1
2 0 1
3 2 1 0 4
4 6 3 2 0 8 9 1 7 5

Note

For $n = 2$ there are $2$ sequences of pillar heights:

• $[0, 1]$ — cost of construction is $0 \oplus 1 = 1$.
• $[1, 0]$ — cost of construction is $1 \oplus 0 = 1$.

For $n = 3$ there are $6$ sequences of pillar heights:

• $[0, 1, 2]$ — cost of construction is $\max(0 \oplus 1, 1 \oplus 2) = \max(1, 3) = 3$.
• $[0, 2, 1]$ — cost of construction is $\max(0 \oplus 2, 2 \oplus 1) = \max(2, 3) = 3$.
• $[1, 0, 2]$ — cost of construction is $\max(1 \oplus 0, 0 \oplus 2) = \max(1, 2) = 2$.
• $[1, 2, 0]$ — cost of construction is $\max(1 \oplus 2, 2 \oplus 0) = \max(3, 2) = 3$.
• $[2, 0, 1]$ — cost of construction is $\max(2 \oplus 0, 0 \oplus 1) = \max(2, 1) = 2$.
• $[2, 1, 0]$ — cost of construction is $\max(2 \oplus 1, 1 \oplus 0) = \max(3, 1) = 3$.