There's a popular mobile game app in which the goal is to join coloured dots on a grid. You start with a board like the one below left. Your job is to draw a path from each dot to its partner of the same colour, making sure you use all the available grid spaces, as shown in the picture below right.

The two pictures above represent a win. The picture on the right represents a loss. In this case, all the dots are joined correctly, but not all of the grid spaces have been filled. This board actually has three correct solutions.

The input will contain ~10~ boards for the game described above. The boards will always be square with a size ranging from ~5 \times 5~ to ~7 \times 7~. Each board has only one possible winning solution. The different coloured dots will be represented as sequential digits starting at ~1~ up to a maximum of ~9~, and the empty grid spaces will be represented with a dot character . (ASCII value ~46~). There will be no spacing between board squares and no blank lines between boards.

Your job is to output the winning solution for each board. Each path should be represented using the number of the two dots the path is joining, as shown in the sample solutions below. You should have a single blank line separating each board in the output. You will have ~10~ seconds to compute the solution for each board. If at any point a solution to a test case takes longer than ~10~ seconds to compute, scoring will stop immediately and you will be awarded the points you have accumulated so far.

Note that in the sample data, there are only ~5~ boards but the judging files will contain ~10~ boards each.

Sample Input

.....
.1.12
.....
32.43
....4
1....
.....
..2..
324.1
4...3
123.45
....6.
..3...
..4...
1.6...
2.5...
.12..3
......
..45.3
...6.2
.54.61
......
......1
.....23
.2.....
...45..
..4.6..
....36.
.....15

Sample Output

22222
21112
22333
32343
33344

11111
33331
32231
32431
44433

123445
123465
123465
124465
126665
225555

112223
155523
154523
154622
154661
111111

1111111
1222223
1233333
1334555
1344665
1333365
1111115

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org