Mr. Ed is visiting his pals at Cuba; in particular he wants to have a nice chat with Yonny, who is a very talented domino player. After taking a few rounds of rum, everybody got ready to play domino. As Mr. Ed and Yonny are close friends, they make an invincible team at domino. They won every single game against their friends, so they started to get bored of playing. “Do you feel you play domino as good as a true Cuban?” — asked Yonny. “I play even better” — presumed Mr. Ed. Now Yonny has challenged Mr. Ed to complete the following task: “I have a wood board divided in n rows of m columns such that there are n × m squares of equal size on it. The challenge is simple: use as many dominoes as you want to cover each single square in the board without overlapping, but not so fast, that will be pretty easy, right? There are some squares colored in black, you cannot put a domino on this squares. Here, let me show you an example.” “Just because you are my friend, I will let you cut some domi- noes in half if you have trouble completing the challenge, but for every domino you cut, you shall pay a small fee to buy more dominoes for me.” As you may expect, now Mr. Ed is all fired up trying to beat Yonny’s challenge, so he is trying to answer: which is the minimum number of dominoes he needs to cut in order to fill every single non-black square in the n × m wood board? Input The input will contain several test cases. The first line of each test case contains 2 integers n and m (1 ≤ n ≤ 20 and 1 ≤ m ≤ 1, 000), representing the number of rows and columns in the board. Each of the next n lines contains m characters describing each square in the wood board: ‘.’ means there is an empty square and ‘#’ means there is a black square in the wood board. The last test case is followed by a single line containing 2 zeroes. Output For each test case, print the number of required cuts to complete the Cuban challenge (see format below). Sample Input 34 ...# ..#. #.#. 34 ...# ..#. ##.. 00
2/2 Sample Output Case #1: 0 Case #2: 1