A New Chess Piece

All submissions for this problem are available.
A New Chess Piece
We have introduced a new chess piece which can move only a single square at once to his left, right, upperleft or upperright as shown in the figure
View Image Here
The chess board can be considered as a rectangle of M rows by N columns of unit squares.
What is the maximum number of these pieces that can be placed on a chess board of size M*N such that all the pieces are safe from each other?
Some squares of chess board are already occupied and cannot be used for placing this new piece.
Input:
The first line of input gives the number of cases, T. T test cases follow. Each case consists of two parts.
The first part is a single line with two integers M and N (1 ≤ M ≤ 80 , 1 ≤ N ≤ 80): The height and width of the chess board.
The second part will be exactly M lines, with exactly N characters in each of these lines. Each character is either a '.' (The square is empty) or 'x' (the square is occupied by some other piece and cannot be used).
Output:
For each test case, output one line containing "Case #X: Y", where X is the case number, starting from 1, and Y is the maximum possible number of these new chess pieces that can be placed on the chess board.
Sample Test Case:
Input:
4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....
Output:
Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46
Author:  csaapogee 
Tags  csaapogee 
Date Added:  15032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 