There is an M x N board, two types of tiles are available, and each of them is infinitely many, you have to place maximum number of non-overlapping tiles in the board. The tiles are given below:
 |
 |
|---|
You cannot rotate or flip any tile. Some cells in the board may be broken; you can't place any part of a tile in the broken cells.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing two integers: M N (2 ≤ M ≤ 8, 2 ≤ N ≤ 100). Each of the next M lines contains N characters forming the board. There are two types of characters. A . means the cell is not broken; a # means that the cell is broken.
Output
For each case, print the case number and maximum number of tiles that can be placed in the board.
Sample
| Sample Input | Sample Output |
|---|---|
3 2 3 ... ... 2 3 ..# ... 5 6 .#.... ...... ...... ....#. ..#... | Case 1: 1 Case 2: 0 Case 3: 3 |