## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ to $n$ exactly once. For example, the sequences $\left[3,1,4,2\right]$, [$1$] and $\left[2,1\right]$ are permutations, but $\left[1,2,1\right]$$\left[0,1\right]$ and $\left[1,3,4\right]$ 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\le i\le n$), at least one of its neighboring elements (standing to the left or right of ${p}_{i}$) must be ${p}_{i}+1$, or ${p}_{i}-1$.
• the permutation must have no fixed points. That is, for every $i$ ($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 $n=4$. Then [$4,3,1,2$] is a funny permutation, since:

• to the right of ${p}_{1}=4$ is ${p}_{2}={p}_{1}-1=4-1=3$;
• to the left of ${p}_{2}=3$ is ${p}_{1}={p}_{2}+1=3+1=4$;
• to the right of ${p}_{3}=1$ is ${p}_{4}={p}_{3}+1=1+1=2$;
• to the left of ${p}_{4}=2$ is ${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\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\le n\le 2\cdot {10}^{5}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $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 $\left[1,2,3\right]$$\left[1,3,2\right]$$\left[2,1,3\right]$$\left[3,2,1\right]$ have fixed points, and in $\left[2,3,1\right]$ and $\left[3,1,2\right]$ the first condition is met not for all positions.