Rooks

You are given a chessboard of size N×N with rooks placed on it.

Your task is to color the rooks using the minimum number of colors so that no two rooks of the same color are in the same row or column.

Input

The first line of the input contains the integer N (1 ≤ N ≤ 100). The next N lines describe the chessboard as an N×N matrix. An empty square is represented by the symbol '.', and a square with a rook is represented by the symbol '*'. There are no spaces between symbols on a single line.

Output

On the first line of the output, print M, the minimum number of colors needed. In the following N lines, print the chessboard where an empty square is represented by the number 0, and a rook colored with color number K is represented by the number K.

Examples