34521번 - !제곱수 순열 스페셜 저지

문제

팔마는 제곱수 순열 문제를 풀기로 했다. 며칠을 투자해도 문제가 잘 풀리지 않아서 열을 받은 팔마는 문제 일부를 몰래 고친 다음 제곱수 순열 문제를 푼 척할 것이다.

1ドル$부터 $N$까지의 정수를 한 번씩만 사용하여 다음 조건을 만족하는 수열 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$을 구해보자.

• $A_i + A_{i + 1}$은 제곱수가 아니다. $(1 \le i \lt N)$

입력

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

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

출력

각 테스트 케이스마다 주어진 순서대로 다음과 같이 출력한다.

• 조건을 만족하는 수열이 있다면, 첫 번째 줄에 수열 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$을 공백으로 구분하여 출력한다. 가능한 수열이 여러 개라면 그중 아무것이나 출력한다.
• 조건을 만족하는 수열이 없다면, 첫 번째 줄에 -1을 출력한다.

제한

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

힌트