# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* moonlight_cl25

*iceknight1093*

**Tester and Editorialist:**# DIFFICULTY:

1158

# PREREQUISITES:

None

# PROBLEM:

Given N, find the lexicographically maximum permutation P of \{1, 2, \ldots, N\} such that \gcd(P_1, P_3, \ldots) \gt \gcd(P_2, P_4, \ldots); or claim that none exist.

# EXPLANATION:

If N is even, the answer is just [N, N-1, \ldots, 3, 2, 1]; i.e, the numbers from 1 to N in descending order.

Itâ€™s easy to see that this satisfies the condition:

- \gcd(P_1, P_3, P_5, \ldots, P_{N-1}) = \gcd(N, N-2, N-4, \ldots, 4, 2) = 2, since all these numbers are even.
- \gcd(P_2, P_4, \ldots, P_N) = 1 since P_1 = 1.
- This is the lexicographically maximum permutation.

If N is odd, the answer is `-1`

: no valid permutation exists.

## Proof

We want \gcd(P_1, P_3, \ldots) \gt \gcd(P_2, P_4, \ldots); in particular \gcd(P_1, P_3, \ldots) \gt 1 must be true.

So, there should be some integer k\gt 1 that divides all integers placed at odd positions.

There are \left \lceil \frac{N}{2} \right\rceil odd positions, and the numbers placed there need to be distinct.

So, at the very least we need integers k, 2k, 3k, 4k, \ldots, k\cdot \left \lceil \frac{N}{2} \right\rceil to be \leq N.

However, this is not possible for k \gt 1, and we reach a contradiction.

So, no valid permutation exists.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
if n%2 == 1: print(-1)
else: print(*list(reversed(range(1, n+1))))
```