폴리오미노의 Jinxiety

폴리오미노는 정사각형 격자 위에서 서로 연결된 단위 정사각형들의 집합이다. 아래 그림은 폴리오미노 예시 4개를 보여준다.

폴리오미노 $P$는 임의의 수직선 또는 수평선과의 교집합이 선분이면 볼록하다. 그림에서 (a)와 (b)는 볼록하고, (c)와 (d)는 볼록하지 않다.

두 정사각형은 변을 공유하면 인접하다고 한다. 볼록한 폴리오미노에서는 두 방향만 사용해 인접한 정사각형으로 이동하면, 임의의 정사각형에서 다른 임의의 정사각형으로 갈 수 있다. 아래 그림은 폴리오미노 (b)에서 이런 경로의 예를 보여준다.

볼록한 폴리오미노 $P$에 대해 jinxiety $J(P)$를 정의한다. $J(P)$는 두 방향만 사용하고 방향을 최대 $k$번 바꾸는 경로로 임의의 정사각형에서 다른 임의의 정사각형으로 갈 수 있게 하는 최소의 $k$이다. 예를 들어 폴리오미노 (a)의 $J(P)$는 1이고, (b)의 $J(P)$는 2이다.

주어진 볼록한 폴리오미노의 jinxiety를 구하시오.

입력에는 여러 테스트 케이스가 들어 있다. 각 테스트 케이스의 첫 줄에는 폴리오미노의 행 수 $h$와 열 수 $w$가 주어진다($1 \le h, w \le 2000$). 이어지는 $h$개의 줄에는 각각 $w$개의 문자가 주어진다. 빈 칸은 ., 폴리오미노의 칸은 #로 나타낸다. 주어지는 도형은 볼록한 폴리오미노임이 보장된다.

입력의 마지막 줄은 $h = w = 0$이다. 모든 폴리오미노 설명에 나오는 문자의 총 개수는 $4\cdot10^6$ 이하이다. 테스트 케이스는 최대 $40\,000$개이다.

각 테스트 케이스마다 주어진 폴리오미노의 jinxiety를 한 줄에 정수 하나로 출력한다.