Mirror Installation

Chaeyoung likes looking in mirrors, so her house has several places where mirrors can be installed.

Her new house has exactly two doors. She wants to install mirrors so that a beam of light starting from one door can reach the other door.

Given the layout of the house, find the minimum number of mirrors that must be installed to make one door visible from the other.

Each mirror must be installed diagonally at a 45-degree angle. Every mirror is double-sided, so it can reflect light from either side. Assume that there are enough mirrors available.

Every input is guaranteed to have at least one way to connect the two doors.

The first line contains the size of the house, N (2 <= N <= 50). The next N lines each contain a string of length N describing the house.

Each character has the following meaning.

• #: a door. There are always exactly two doors.
• .: an empty cell. Light can pass through it.
• !: a cell where a mirror can be installed. Light can also pass through it.
• *: a wall. Light cannot pass through it.

Print the minimum number of mirrors that must be installed so that one door can see the other door.