30667번 - 제곱수 원순열 스페셜 저지

$1$부터 $N$까지의 정수를 한 번씩만 사용하여 다음 조건을 만족하는 수열 $A_1$, $A_2$, $\cdots$, $A_N$을 출력하시오.

• $A_i + A_{i + 1}$은 제곱수이다. $(1 \le i \lt N)$
• $A_1 + A_N$은 제곱수이다.

총 $T$개의 테스트 케이스가 입력으로 주어지며, 첫 번째 줄에 $T$가 주어진다.

그 다음 줄부터 각 테스트 케이스마다 하나의 줄에 양의 정수 $N$이 주어진다.

각 테스트 케이스마다 주어진 순서대로 한 개의 줄에,

• 조건을 만족하는 수열이 있다면 수열 $A_1$, $A_2$, $\cdots$, $A_N$을 공백으로 구분하여 출력한다.
• 조건을 만족하는 수열이 없다면 -1을 출력한다.

• $1 \le T \le 5\,000$ 
• $2 \le N \le 10^7$
• 모든 테스트 케이스의 $N$의 합은 $10^7$을 넘지 않는다.