Placing Rooks

A rook moves along its own row or column to any square it can reach. Two rooks capture each other when they share a row or a column with nothing in between.

Placing as many non capturing rooks as possible on an empty N × N board is easy. Put one on each square of a diagonal, N in total.

Now add pawns. A rook cannot move through the square a pawn stands on, so a row or a column can hold several rooks as long as a pawn sits between them. Given a board with pawns on it, find the largest number of rooks that can be placed so that no two of them capture each other.

A rook is placed only on an empty square.

The first line contains the board size N. (1 ≤ N ≤ 100)

Each of the next N lines contains one string of length N. A '.' is an empty square and an 'X' is a square with a pawn on it.

Print the largest number of rooks that can be placed.