Permutación Potente (Editorial)

Solución

La paridad de la expresión p_i^{p_{i+1}} depende solo de $p_i$, es decir, p_i^{p_{i+1}} \equiv p_i (\bmod p_i), por lo tanto, el problema se reduce a para qué $n$ la cantidad de pares e impares en el rango [1,n-1] es igual y esto sucede solo cuando $n$ es impar y en ese caso el orden de la permutación no importa, de lo contrario, si $n$ es par, entonces no hay opción válida.

for _ in range(int(input())):
   n=int(input())
   if(n%2==0):
      print(-1)
   else:
      print(*[i for i in range(1,n+1)])

Complejidad $\mathcal{O}(n)$