Given a chessboard N × N , on which the rooks are placed. You have to color those rooks in a minimal
number of colors in that way no horizontal and vertical line contains two rooks of the same color.
Input
First line of the input file contains an integer S (0 < S < 10) that indicates how many sets of inputs are there. The description of each set is given below:
The first line of each input set contains number N (0 ≤ N ≤ 100).
The next N lines contain a chessboard (array N × N ), where an empty cell is marked as ‘.’, and a cell that contains a rook is marked as ‘*’ (there are not blanks between the symbols in a line).
Output
The description of output for each test case is given below:
The first line of the output for each test case contains number M – the minimal number of colors. The next N lines contain a chessboard, where an empty cell is marked as ‘0’, and a cell that contains a rook is marked as ‘K’, where K is a color of the rook. There can be more than correct solution any valid solution will be accepted.
Sample Input
2
2
*.
**
4
*.*.
*.*.
***.
..**
Sample Output
2
20
12
4 1020 3010 2130 0041