블록 퍼즐

블록 퍼즐은 단위 정사각형으로 나뉜 정사각형 격자에서 하는 게임이다. 칸 가운데 일부는 시작칸으로 표시되어 있고, 한 칸은 도착칸으로 표시되어 있다.

게임은 시작칸 하나에 $1 \times 1 \times 2$ 블록을 세워 놓으면서 시작한다. 이때 블록의 $1 \times 1$ 면이 그 칸에 닿아야 한다. 게임의 목표는 블록을 적절히 굴려서 도착칸에 세우는 것이다. 즉 $1 \times 1$ 면이 도착칸에 닿아 있게 만들면 된다.

블록은 굴려서 움직인다. $1 \times 1$ 면이 격자에 닿아 있으면 네 방향 모두로 굴릴 수 있다. 하지만 $2 \times 1$ 면이 격자에 닿아 있으면 $1 \times 1$ 면이 격자에 닿도록만 굴릴 수 있다. 즉 언제나 길이가 1인 변을 축으로 삼아 굴려야 한다.

아래 그림은 굴릴 수 있는 방법을 모두 나타낸 것이고, 굴리기 직전 상태를 반투명으로 그렸다.

이 게임이 어려운 이유는 일부 칸에 구멍이 뚫려 있기 때문이다. 블록의 바닥면이 모두 구멍 위에 있으면 블록은 구멍으로 떨어지고 게임에서 진다. 바닥면이 $2 \times 1$ 이고 두 칸 가운데 한 칸에만 구멍이 있다면 블록은 떨어지지 않는다. 블록은 게임판의 경계에 걸칠 수도 있다. 즉 바닥면이 $2 \times 1$ 일 때 한 칸은 게임판 안에, 다른 한 칸은 게임판 밖에 있어도 된다.

홍준이는 이 게임을 너무 많이 해서 지루해졌다. 그래서 게임을 풀 수 없게 만들려고 구멍을 더 뚫어 보려고 한다. 홍준이는 시작칸과 도착칸이 아닌 칸을 구멍으로 만들 수 있다.

게임판의 상태가 주어졌을 때, 게임을 풀 수 없게 만들려면 구멍으로 바꿔야 하는 칸이 최소 몇 개인지 구하는 프로그램을 작성하시오.

첫째 줄에 게임판의 크기 $N$이 주어진다 ($3 \le N \le 50$). 둘째 줄부터 $N$개의 줄에 게임판의 상태가 한 줄에 $N$개의 문자로 주어진다.

'.'은 빈 칸, 'H'는 구멍, 'b'는 시작칸, '$'는 도착칸을 뜻한다.

게임판에 있는 '$'는 정확히 한 개이고, 'b'는 한 개 이상이다.

첫째 줄에 게임을 풀 수 없게 만들려고 구멍으로 바꿔야 하는 칸의 최소 개수를 출력한다. 게임을 풀 수 없게 만들 수 없다면 -1을 출력한다.