[Solution] Funny Permutation Codeforces Solution

B. Funny Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A sequence of 𝑛$n$ numbers is called permutation if it contains all numbers from 1$1$ to 𝑛$n$ exactly once. For example, the sequences [3,1,4,2]$[3,1,4,2]$, [1$1$] and [2,1]$[2,1]$ are permutations, but [1,2,1]$[1,2,1]$, [0,1]$[0,1]$ and [1,3,4]$[1,3,4]$ are not.

For a given number 𝑛$n$ you need to make a permutation 𝑝$p$ such that two requirements are satisfied at the same time:

• For each element 𝑝𝑖$p_i$, at least one of its neighbors has a value that differs from the value of 𝑝𝑖$p_i$ by one. That is, for each element 𝑝𝑖$p_i$ (1≤𝑖≤𝑛$1\le i\le n$), at least one of its neighboring elements (standing to the left or right of 𝑝𝑖$p_i$) must be 𝑝𝑖+1$p_i+1$, or 𝑝𝑖−1$p_i-1$.
• the permutation must have no fixed points. That is, for every 𝑖$i$ (1≤𝑖≤𝑛$1\le i\le n$), 𝑝𝑖≠𝑖$p_i\ne i$ must be satisfied.

Let's call the permutation that satisfies these requirements funny.

For example, let 𝑛=4$n=4$. Then [4,3,1,2$4,3,1,2$] is a funny permutation, since:

• to the right of 𝑝1=4$p_1=4$ is 𝑝2=𝑝1−1=4−1=3$p_2=p_1-1=4-1=3$;
• to the left of 𝑝2=3$p_2=3$ is 𝑝1=𝑝2+1=3+1=4$p_1=p_2+1=3+1=4$;
• to the right of 𝑝3=1$p_3=1$ is 𝑝4=𝑝3+1=1+1=2$p_4=p_3+1=1+1=2$;
• to the left of 𝑝4=2$p_4=2$ is 𝑝3=𝑝4−1=2−1=1$p_3=p_4-1=2-1=1$.
• for all 𝑖$i$ is 𝑝𝑖≠𝑖$p_i\ne i$.

For a given positive integer 𝑛$n$, output any funny permutation of length 𝑛$n$, or output -1 if funny permutation of length 𝑛$n$ does not exist.

Input

The first line of input data contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases.

The description of the test cases follows.

Each test case consists of f single line containing one integer 𝑛$n$ (2≤𝑛≤2⋅105$2\le n\le 2\cdot {10}^5$).

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, print on a separate line:

• any funny permutation 𝑝$p$ of length 𝑛$n$;
• or the number -1 if the permutation you are looking for does not exist.

Note

The first test case is explained in the problem statement.

In the second test case, it is not possible to make the required permutation: permutations [1,2,3]$[1,2,3]$, [1,3,2]$[1,3,2]$, [2,1,3]$[2,1,3]$, [3,2,1]$[3,2,1]$ have fixed points, and in [2,3,1]$[2,3,1]$ and [3,1,2]$[3,1,2]$ the first condition is met not for all positions.