Woburn Challenge 1995

A square arrangement of numbers such as

1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4

is a Latin square because each whole number 1, 2, 3, 4 and 5 appears exactly once in each row and column of the square.

Of all the possible ~5 \times 5~ Latin squares, the one above is the smallest in the following sense: if the digits are strung together (in rows from top to bottom) the resulting integer,

$$\displaystyle 12345\ 21453\ 34512\ 45231\ 53124$$

is the smallest one possible.

Input Specification

On the first line is ~M~, an integer indicating the number of test cases.
On each of the next ~M~ lines is an integer ~N~ between 2 and 9.

Output Specification

Output the smallest ~N \times N~ Latin square for each test case.

Sample Input

1
5

Sample Output

1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4