Patisserie ACM

Amber, a pastry chef, opened her own shop last month. To promote it she decided to enter the International Chocolate Patissier Competition, where she has been perfecting a recipe for sweet chocolate bars. After thousands of attempts she finally nailed the recipe. Shaping the chocolate into a neat rectangle, however, takes great skill, and this time she ended up with another oddly shaped bar like the one in Figure G-1.

Figure G-1: A strangely shaped chocolate bar

Each chocolate bar is made of many small rectangular chocolate segments. Adjacent segments are separated by a groove so they can be snapped apart easily. Amber wants to cut each oddly shaped bar into rectangular pieces to sell in her shop, following these rules:

• Every cut must run along a groove.
• Every resulting piece must be rectangular.
• The bar must be split into as few pieces as possible.

Under these rules, Figure G-2 is a valid way to cut the bar in Figure G-1. Figures G-3 and G-4 are invalid: G-3 leaves a non-rectangular piece, and G-4 produces more pieces than G-2.

Figure G-2: A cutting that obeys the rules

Figure G-3: A cutting that leaves a non-rectangular piece

Figure G-4: A cutting that produces more pieces than Figure G-2

Write a program that computes the minimum number of pieces the bar is divided into when it is cut according to the rules.

The input consists of several datasets, each describing one chocolate bar.

The first line of a dataset contains two integers $h$ and $w$ ($2 \le h \le 100$, $2 \le w \le 100$), the height and width of the bar measured in segments. Each of the next $h$ lines contains $w$ characters describing one row of the grid. The character at row $i$, column $j$ means:

• # — a chocolate segment is present at that position;
• . — no chocolate is present there.

Every dataset is guaranteed to describe a single connected bar with no holes: it never looks like the disconnected bars in Figure G-5 or the bars with holes in Figures G-6 and G-7, and it always contains at least one #.

Figure G-5: Disconnected chocolate bars

Figure G-6: A chocolate bar with a hole

Figure G-7: Another chocolate bar with a hole

The end of the input is a line containing two zeros separated by a space; this line is not part of the data and must not be processed.

For each dataset, output a single line containing one integer: the number of pieces produced when the bar is cut according to the rules. Print nothing else.