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