Marta and Raul love chocolate, relax with a few ounces after dinner. Today they have found a very good offer of chocolate with almonds in the supermarket. Although that is Marta’s favorite, Raul hates finding hard bits when he enjoys chocolate; he prefers it to melt in his mouth, without noticing the almonds. After thinking about it for a while, they have decided to buy a few tablets and divide them so that the ounces with almonds are separated from the ounces without them. The tablets can only be split comfort- ably in horizontal or vertical, by the already marked separations between ounces. Once the tablet is divided into two parts, each one can still be divided by its own. Now they wonder how many cuts they will have to make at least to divide each of the tablets into portions that have only ounces with almonds or ounces without almonds. Input Input consists of a series of descriptions of chocolate tablets. Each begins with a line with two numbers, the number of rows R and columns C in which the tablet is divided into ounces (both between 1 and 20). R lines are then displayed, each with C characters. The character ‘.’ indicates an ounce without almonds and the ‘#’ character indicates an ounce with almonds. Output For each tablet the number of cuts needed to separate the ounces with almonds from the ones that do not have them will be written in a line. Note: The figure on the right shows an optimal division of the tablet of the first test case, where 7 cuts are required. Sample Input 55 .##.. .#### ##... ..... ..### 16 ...### 22 #. .# Sample Output 7 1 3