This is the hard version of the problem. The difference between the versions is that in this version, $1 \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 positive integer $n$. Find some permutation$^{\text{∗}}$ $p$ of length $n$ such that for every $i$ ($\style{color:red}{1 \le i \le n-1}$) there exists $j$ ($\style{color:red}{i \le j \le n}$) such that $p_i = p_j \oplus i$ $^{\text{†}}$, or determine that it does not exist.

$^{\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 one positive integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the permutation.

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

Output

For each test case, if there is a suitable permutation, output $n$ integers $p_1,p_2,\ldots,p_n$ — the permutation $p$. Otherwise, output $-1$.

If multiple solutions exist, output any of them.

Note

In the first test case, the permutation $p = [2,1,3]$ fulfills the condition, as $p_2 = 1$ and $p_3 \oplus 2 = 1$.

In the second test case, there is no suitable permutation.