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