D. Doubled Sequence II
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let's be direct. No stories, no worries. You will be given an integer $$$n$$$ and you must determine if there is a sequence $$$a$$$ of length $$$2n$$$ such that:

  • Each value from $$$1$$$ to $$$n$$$ occurs exactly twice in $$$a$$$.
  • For each $$$i = 1, \ldots, n$$$, the distance between both of its occurrences is exactly $$$i + 1$$$. This is, let $$$L_{i}$$$ and $$$R_{i}$$$ be the leftmost and rightmost occurrence of $$$i$$$, respectively. Then, $$$R_{i} - L_{i} = i + 1$$$.

If there is at least one sequence, print it. Otherwise, print -1.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^{5}$$$) — The number of testcases.

The following $$$t$$$ lines contain an integer $$$n_{i}$$$ ($$$1 \leq n_{i} \leq 10^{6}$$$) — The value of $$$n$$$ of the $$$i$$$-th query.

It is guaranteed that the sum of $$$n_{i}$$$ doesn't exceed $$$2 \cdot 10^{6}$$$.

Output

For each query, print a single line — Print -1 if there is no sequence that holds the conditions or $$$2n$$$ integers separated by a space representing a valid sequence.

Example
Input
5
1
2
3
4
7
Output
-1
-1
2 3 1 2 1 3
2 3 4 2 1 3 1 4
1 5 1 6 3 7 4 5 3 2 6 4 2 7