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.

XOR-convenience (Hard Version)

Examples