Background

youyou is very weak, but he really likes constructing strange sequences.

Problem Description

This problem uses Special Judge.

youyou likes sequences very much, so he wants you to construct a positive integer sequence $\{a_i\}$ of length $n$.

youyou likes XOR, so he requires the constructed sequence to satisfy $a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_{n-1} \oplus a_n = n$ (where $\oplus$ denotes XOR).

youyou really hates identical numbers, so he requires that all numbers in the sequence are pairwise distinct.

But youyou does not want the numbers in this sequence to be too large, so he requires that the sum of all numbers in the sequence does not exceed $n^2$, i.e., $\displaystyle\sum_{i=1}^n a_i \le n^2$.

Now you need to construct a sequence that satisfies all of youyou's requirements. If there is no solution, output -1. If there are multiple answers, output any one of them.

You need to answer $T$ test cases.

Input Format

The first line contains a positive integer $T$.

The next $T$ lines each contain an integer $n$, meaning you need to construct a required sequence of length $n$.

Output Format

Output $T$ lines in total.

If the $i$-th line corresponds to constructing a sequence of length $n$, then output exactly $n$ numbers on that line, representing your constructed sequence. Note that every number in the sequence must be a positive integer. If such a sequence cannot be constructed, output -1 on this line.

3
1
2
5

1
3 1
1 4 5 3 6

Hint

Sample Explanation

For $n = 1$, one feasible solution is $\{1\}$.

For $n = 2$, one feasible solution is $\{3,1\}$.

For $n = 5$, one feasible solution is $\{1,4,5,3,6\}$, because $1 ⊕ 4 ⊕ 5 ⊕ 3 ⊕ 6 = 5$, and $1+4+5+3+6 =19\le 5^2$, and all numbers in the sequence are also pairwise distinct.

Constraints

For $5\%$ of the testdata, $n \le 5$.

For $15\%$ of the testdata, $n \le 10$.

For $40\%$ of the testdata, $n \le 1000$.

For $70\%$ of the testdata, $n \le 10^5$.

For $100\%$ of the testdata, $1 \le n \le 5 × 10^5$, and $1 \le T \le 10$.

Translated by ChatGPT 5