34347번 - 제곱수 순열$^2$ 스페셜 저지

문제

당신은 다음 조건을 만족하는 길이 $N$의 순열 $A=[A_1,A_2,\cdots,A_N], B=[B_1,B_2,\cdots,B_N]$을 찾아야 한다.

• 1ドル\le i<N$인 모든 정수 $i$에 대해 $A_i^{ B_i} \times A_{i+1}^{ B_{i+1}}$가 제곱수이다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 100)$

각 테스트 케이스의 첫째 줄에 양의 정수 $N$이 주어진다. $(2\le N\le 5,000円)$

모든 테스트 케이스에서 $N$의 합은 5ドル,000円$을 넘지 않는다.

출력

각 테스트 케이스의 첫째 줄에 순열 $A, B$가 존재한다면 YES를, 존재하지 않는다면 NO를 출력한다.

YES를 출력하였다면 둘째 줄에 $A_1, A_2, \cdots, A_N$을 공백으로 구분하여 출력한다.

YES를 출력하였다면 셋째 줄에 $B_1, B_2, \cdots, B_N$을 공백으로 구분하여 출력한다.

답이 여러 개 있다면, 그중 하나를 아무 것이나 출력한다.

제한

노트

길이 $N$의 순열이라는 것은 1ドル$부터 $N$까지의 모든 양의 정수가 한 번씩만 등장하는 수열을 말한다.