파티세리 ACM

제빵사 앰버(Amber)는 지난달 자신의 가게를 열었다. 가게를 홍보하기 위해 그녀는 국제 초콜릿 파티시에 대회에 출전하기로 했고, 달콤한 초콜릿 바 레시피를 다듬어 왔다. 수천 번의 시도 끝에 마침내 레시피를 완성했다. 하지만 초콜릿을 반듯한 직사각형 모양으로 굳히는 데에는 높은 숙련도가 필요했고, 이번에도 그림 G-1처럼 이상한 모양의 초콜릿 바가 만들어지고 말았다.

그림 G-1: 이상한 모양의 초콜릿 바

각 초콜릿 바는 작은 직사각형 초콜릿 조각 여러 개가 모여 이루어진다. 서로 맞닿은 조각 사이에는 쉽게 쪼갤 수 있도록 홈(groove)이 파여 있다. 앰버는 이상한 모양의 초콜릿 바를 직사각형 조각들로 잘라 가게에서 팔려고 한다. 자르는 규칙은 다음과 같다.

• 모든 절단은 홈을 따라 이루어져야 한다.
• 잘린 각 조각은 반드시 직사각형이어야 한다.
• 초콜릿 바를 가능한 한 적은 수의 조각으로 나누어야 한다.

이 규칙을 따르면 그림 G-2는 그림 G-1의 초콜릿 바를 올바르게 자른 예이다. 그림 G-3과 G-4는 규칙에 어긋난다. 그림 G-3에는 직사각형이 아닌 조각이 있고, 그림 G-4는 그림 G-2보다 더 많은 조각으로 나뉜다.

그림 G-2: 규칙을 따르는 절단의 예

그림 G-3: 직사각형이 아닌 조각이 남는 절단의 예

그림 G-4: 그림 G-2보다 조각이 더 많아지는 절단의 예

규칙에 따라 초콜릿 바를 잘랐을 때 나오는 조각의 최소 개수를 계산하는 프로그램을 작성하라.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋은 초콜릿 바 하나를 나타낸다.

각 데이터셋의 첫 줄에는 두 정수 $h$와 $w$가 주어진다 ($2 \le h \le 100$, $2 \le w \le 100$). 이는 각각 조각 단위로 잰 초콜릿 바의 세로 길이와 가로 길이이다. 이어지는 $h$개의 줄에는 각각 $w$개의 문자가 있어 격자의 한 행을 나타낸다. $i$번째 행 $j$번째 열의 문자는 다음을 의미한다.

• # — 그 위치에 초콜릿 조각이 있다.
• . — 그 위치에 초콜릿이 없다.

모든 데이터셋은 구멍이 없는 하나의 연결된 초콜릿 바를 나타냄이 보장된다. 즉, 그림 G-5처럼 서로 떨어진 바가 되거나 그림 G-6, G-7처럼 구멍이 뚫린 모양이 되는 경우는 없으며, 각 데이터셋에는 # 문자가 적어도 하나 있다.

그림 G-5: 서로 떨어진 초콜릿 바

그림 G-6: 구멍이 뚫린 초콜릿 바

그림 G-7: 구멍이 뚫린 초콜릿 바의 또 다른 예

입력의 끝은 공백으로 구분된 두 개의 0으로 이루어진 줄로 표시된다. 이 줄은 데이터가 아니므로 처리하지 않는다.

각 데이터셋에 대해, 규칙에 따라 초콜릿 바를 잘랐을 때 나오는 조각의 개수를 정수 하나로 한 줄에 출력한다. 그 외의 다른 문자는 출력하지 않는다.