Clash of the Titans#380
Sashko is passionate about programming computer games. For three days, he has been developing a new mobile phone game called Clash of the Titans. The heroes of the game are tin soldiers. As a prototype for the tin soldiers' movements, Sashko used a chess rook.
A chess rook is a piece that can move any number of squares vertically or horizontally. Rooks cannot move through obstacles. The task is to calculate the maximum number of rooks that can be placed on the board so that no two attack each other. This means the configuration is correct if no two rooks are on the same row or column within sight of each other.
The following example shows five images. The first image is empty, the second and third images show correct configurations, and the fourth and fifth images are examples of incorrect configurations.
Help Sashko finish his program as quickly as possible and calculate the maximum number of rooks for the given board configuration.
The first line of the input file contains an integer representing the size of the board, not exceeding . The following lines contain the description of the chessboard, where the character '.' indicates an empty cell, and the uppercase character 'X' indicates an obstacle. There are no spaces in the input file.
Output the maximum number of rooks for a correct configuration of the board.
Example 1