This is the easy version of the problem. The difference between the versions is that in this version, $2 \le i \le n-1$. Note that a correct solution for the hard version is not necessarily a correct solution for the easy version.

Given a natural number $n$. Find a permutation$^{\text{∗}}$ $p$ of length $n$, such that for each $i$ ($\style{color:red}{2 \le i \le n-1}$) there exists a $j$ ($\style{color:red}{i \le j \le n}$) such that $p_i = p_j \oplus i$ $^{\text{†}}$.

It can be proven that under the constraints of the problem, there exists at least one suitable permutation $p$.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). $^{\text{†}}$$\oplus$ denotes the bitwise XOR operation.

Input

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

The only line of each test case contains a single integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the permutation.

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

Output

For each test case, output $n$ integers $p_1,p_2,\ldots,p_n$ — the permutation $p$.

If there are multiple solutions, you may output any of them.

Note

In the first test case, the permutation $p = [2,1,3]$ is suitable since $p_2 = 1$ and $p_3 \oplus 2 = 1$.

In the second test case, the permutation $p = [3,6,2,5,1,4]$ is suitable, as:

• $p_2 = 6 = 4 \oplus 2 = p_6 \oplus 2$
• $p_3 = 2 = 1 \oplus 3 = p_5 \oplus 3$
• $p_4 = 5 = 1 \oplus 4 = p_5 \oplus 4$
• $p_5 = 1 = 4 \oplus 5 = p_6 \oplus 5$