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 1234521453345124523153124}$$

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