여덟 퀸으로 부족할 때, N 퀸

여덟 퀸 퍼즐은 8x8 판 위에 퀸 여덟 개를 서로 공격하지 않게 놓는 문제다. N 퀸 문제는 NxN 판과 퀸 N개로 같은 것을 묻는다.

두 퀸은 같은 행에 있거나, 같은 열에 있거나, 같은 대각선 위에 있으면 서로 공격한다. 행과 열에는 $0$부터 번호를 매긴다. $(r_1, c_1)$과 $(r_2, c_2)$에 놓인 두 퀸이 같은 대각선 위에 있다는 것은 $r_1 + c_1 = r_2 + c_2$이거나 $r_1 - c_1 = r_2 - c_2$라는 뜻이다.

올바른 배치에는 행마다 퀸이 정확히 하나, 열마다도 정확히 하나 놓인다. 그래서 배치는 벡터 $p_0, p_1, \dots, p_{N-1}$로 적는다. $p_i$는 $i$번 행에 놓인 퀸의 열 번호이고, 이 벡터는 $0$부터 $N-1$까지의 순열이다.

$N \ge 4$이면 올바른 배치가 둘 이상이므로, 답은 사전순으로 가장 작은 벡터 하나로 정한다. 두 벡터를 비교할 때는 $0$번 자리부터 훑으면서 값이 처음 달라지는 자리를 찾고, 그 자리의 값이 작은 쪽이 사전순으로 더 작다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 20$). 다음 $T$개의 줄에는 각각 정수 $N$이 하나씩 주어진다 ($4 \le N \le 18$).

테스트 케이스마다 주어진 순서대로 두 줄씩 출력한다. 첫 줄에는 $N$을 출력한다. 둘째 줄에는 그 판에서 사전순으로 가장 작은 벡터, 즉 열 번호 $p_0, p_1, \dots, p_{N-1}$을 공백 하나로 구분해 출력한다.