CF2189C2.XOR-convenience (Hard Version)

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.

这是该问题的困难版本。两个版本的区别在于：在本版本中，$1 \le i \le n-1$。注意，困难版本的一个正确解法不一定适用于简易版本。

给定一个正整数 $n$。请构造一个长度为 $n$ 的排列$^{\text{∗}}$ $p$，使得对每个 $i$（\style{color:red}{1 \le i \le n-1}），均存在某个 $j$（\style{color:red}{i \le j \le n}），满足 $p_i = p_j \oplus i$ $^{\text{†}}$；若不存在这样的排列，则判定其不存在。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

$^{\text{†}}$ $\oplus$ 表示按位异或运算。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅一行，包含一个正整数 $n$（$3 \leq n \leq 2 \cdot 10^5$）——即排列的长度。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

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.

对于每个测试用例，如果存在合适的排列，则输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$ —— 即排列 $p$；否则，输出 $-1$。

如果存在多个解，输出任意一个即可。

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.

在第一个测试用例中，排列 $p = [2,1,3]$ 满足条件，因为 $p_2 = 1$ 且 $p_3 \oplus 2 = 1$。

在第二个测试用例中，不存在满足条件的排列。