## WC '95 P3 - Smallest Latin Square

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type
##### 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 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,

is the smallest one possible.

#### Input Specification

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

#### Output Specification

Output the smallest 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