거울 설치

채영이는 거울 보는 것을 좋아해서 집 곳곳에 거울을 둘 수 있는 자리를 마련해 두었다.

새 집에는 문이 정확히 두 개 있다. 채영이는 거울을 적절히 설치하여 한 문에서 출발한 빛이 다른 문까지 도달하게 하려고 한다.

집의 구조가 주어질 때, 한 문에서 다른 문을 볼 수 있게 하려면 설치해야 하는 거울의 최소 개수를 구하라.

거울은 45도 기울어진 대각선 방향으로만 설치할 수 있으며, 양면 거울이므로 어느 방향에서 들어온 빛도 반사할 수 있다. 사용할 수 있는 거울의 수는 충분하다.

항상 두 문을 연결할 수 있는 입력만 주어진다.

첫째 줄에 집의 크기 N (2 <= N <= 50)이 주어진다. 이어지는 N개의 줄에는 집의 상태를 나타내는 길이 N의 문자열이 주어진다.

각 문자는 다음 의미를 가진다.

• #: 문. 항상 정확히 두 곳에 있다.
• .: 빈칸. 빛이 지나갈 수 있다.
• !: 거울을 설치할 수 있는 칸. 빛도 지나갈 수 있다.
• *: 벽. 빛이 지나갈 수 없다.

한 문에서 다른 문을 볼 수 있도록 설치해야 하는 거울의 최소 개수를 출력한다.