Skyline#12306

Skyline

1 second

256 megabytes

Hard

You're given an integer $n$ . You're asked to determine any valid permutation $p$ of ${1, 2, 3, ..., n}$ \{1,2,3,...,n\} such that:

$a_{i} = \frac{p _{i}}{i}$ \displaystyle a_i=\frac{p_i}{i}
if $i$ is even then this must hold $a_{i - 1} < a_{i} > a_{i + 1}$ a_{i-1}<a_i>a_{i+1}
if $i$ is odd then this must hold $a_{i - 1} > a_{i} < a_{i + 1}$ a_{i-1}>a_i<a_{i+1}

If no such permutation exists print $- 1$ .

Input

The first line contains single integer $t$ $(1 \leq t \leq 1000)$ (1 \le t \le 1000) – the number of test cases.

The first line of each test case contains single integer $n$ $(3 \leq n \leq 1 0^{5})$ (3 \le n \le 10^5) – the length of the permutation $p$ .

It's guaranteed that $\sum n \leq 1 0^{5}$ \sum n \le 10^5.

For each test case, if such permutation $p$ exists then output any valid permutation, otherwise output $- 1$ .

Example 1

Loading

{1, 2, 3, ..., n}

a_{i} = \frac{p _{i}}{i}

a_{i - 1} < a_{i} > a_{i + 1}

a_{i - 1} > a_{i} < a_{i + 1}

(1 \leq t \leq 1000)

(3 \leq n \leq 1 0^{5})

\sum n \leq 1 0^{5}

(3 \leq n \leq 6)

(n = 50)

(n = 1 0^{5})