Потужна Перестановка (Розбір)

Рішення

Парність виразу p_i^{p_{i+1}} залежить лише від $p_i$, тобто p_i^{p_{i+1}} \equiv p_i (\bmod p_i), отже, задача зводиться до того, для яких $n$ кількість парних і непарних у діапазоні [1,n-1] є рівною, і це відбувається лише тоді, коли $n$ непарне, і в цьому випадку порядок пермутації не має значення, інакше, якщо $n$ парне, то немає дійсного варіанту.

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

Складність $\mathcal{O}(n)$