Problema TRES

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