제곱수 순열$^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$까지의 모든 양의 정수가 한 번씩만 등장하는 수열을 말한다.