Who needs 8 queens when you can have N?

The eight queens puzzle asks you to place eight queens on an 8x8 board so that no queen attacks another. The N queens problem asks the same thing on an NxN board with N queens.

Two queens attack each other when they share a row, share a column, or sit on a common diagonal. Number the rows and the columns from $0$. Queens at $(r_1, c_1)$ and $(r_2, c_2)$ sit on a common diagonal when $r_1 + c_1 = r_2 + c_2$ or $r_1 - c_1 = r_2 - c_2$.

A valid placement holds exactly one queen in every row and exactly one in every column, so it is written as a vector $p_0, p_1, \dots, p_{N-1}$ in which $p_i$ is the column of the queen in row $i$. That vector is a permutation of $0$ through $N-1$.

Every $N \ge 4$ admits more than one valid placement, so the answer is pinned to the lexicographically smallest vector. To compare two vectors, read them from index $0$ and find the first position where they differ. The vector with the smaller value at that position is the smaller one.

The first line contains the number of test cases $T$ ($1 \le T \le 20$). Each of the next $T$ lines contains one integer $N$ ($4 \le N \le 18$).

Print two lines per test case, in the order the cases are given. The first line contains $N$. The second line contains the lexicographically smallest vector for that board, that is the $N$ column numbers $p_0, p_1, \dots, p_{N-1}$ separated by single spaces.