Clash of the Titans
Sasha fond of computer games. For three days he wrote a new game for cell phone called "Clash of the Titans". Heroes toys were the tin soldiers. As a prototype for the description of actions the soldier Sasha took a chess rook. Chess rook - a figure that can move any number of squares vertically or horizontally. Ferry can not move beyond the obstacles. Problem - to calculate the maximum number of rooks that can be put on the board so that no two are not beating each other. This means that the configuration is correct, provided that no two rooks are not on the same horizontal or vertical within sight of each other. The following example shows five images. The first image is empty, second and third images show the correct configuration, and the fourth and the fifth drawing - examples of incorrect configurations.
Help Sasha quickly finish the program and calculate the maximum number of rooks on a given configuration of the board.
Input In the input file in the first line contains an integer - the size of the board, not exceeding 4. Subsequent lines contain a description of the chessboard, with the character '.' indicates an empty cell, and the uppercase character 'X' indicates the obstacle. In the input file, no gaps. Output In the output file to bring the maximum number of rooks on the correct configuration of the board.