Problem G
Rooks
Input: Standard Input

Output: Standard Output

Time Limit: 8 Seconds 

 

Given a chessboard NxN, 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 NxN), 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                             Output for Sample Input

2
2
*.
**
4
*.*.
*.*.
***.
..**
 
2
2 0
1 2

4

1 0 2 0

3 0 1 0

2 1 3 0

0 0 4 1

 

 

 

Problem source: Russian summer training camp 2000.

Problem author: Maxim Babenko

Problem translation: Dmytro Chernysh