N Knights Problem

All submissions for this problem are available.
Dave recently mastered the problem of placing N queens on a chessboard so
that no two queens attack eachother.
Now he wants to see how many knights he can place on a chessboard so
that no two knights attack eachother.
Normally this would be a simple task, but some of the squares of the
chessboard have been marked as unusable and hence cannot have a knight placed
on them.
Recall that a knight can attack another knight if their vertical distance
is 2 and their horizontal distance is 1, or if their vertical distance is 1 and
their horizontal distance is 2. Only one knight may be placed on each square
of the chessboard
Input
The first line of input contains an integer T (0<T≤50), the number of test cases to follow.
Each test case will begin with a line containing 2 integers M and N (0<M,N≤30),
denoting the number of rows and columns, respectively.
M lines follow, each containing exactly N characters.
The jth character of the ith line is '.' if a knight may be placed in the jth column of the ith
row, and '#' if the square is unusable.
Output
For each test case, output on a single line the maximum number of knights that may be placed
on the chessboard such that no two attack eachother.
Sample input:
2
2 4
....
....
5 5
..#..
#..#.
##...
...##
.....
Sample output:
4 11
The following image represents the chessboard and a possible solution to the second test case:
Author:  pieguy 
Tester:  friggstad 
Editorial  http://discuss.codechef.com/problems/KNIGHTS 
Tags  cook04, medium, pieguy 
Date Added:  9112010 
Time Limit:  0.294118 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TEXT, PYP3 
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. 