Server Time: Wed Nov 14, 2018 1:39 pm
Welcome ( logout
1310 - Tiles (III)
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

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 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 Input

Output for Sample Input

3

2 3

...

...

2 3

..#

...

5 6

.#....

......

......

....#.

..#...

Case 1: 1

Case 2: 0

Case 3: 3

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan