Server Time: Sun Sep 27, 2020 5:40 pm
Welcome ( logout
D - Tiles (III)
PDF (English) Ranklist
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:

t1.png    t2.png

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


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


2 3



2 3



5 6






Case 1: 1

Case 2: 0

Case 3: 3


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