Server Time: Sun Oct 13, 2019 8:59 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.

# 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