Problem Description
When Teddy was a child,he liked playing toy bricks very much.And he had found an interesting way to play with those toy bricks.
There is a big plate with some blocks in it,of course you can't put the bricks in the block,you can only put the the bricks in the place which is empty.
To make the problem easier I only give you one kind of brick:
@
@@@
@
and I will give you the box's initial state as below:
...####..
...###..#
..####..#
...####..
the '#' means the block and the '.' means the empty place.
To play this game,simply,you just need to put as many bricks to the box as you can.
OK,just tell me what is the maximum number of bricks can be put into the box ^_^.
Input
The first line contain a T followed by T cases.
The first line of each case,there are two integers n,m,indicating the Height adn the Width of the box.(n <= 100 , m <= 8).
then n lines strings each with m characters give the initial stae of the box.
There will be one blank line after each case.
Output
One integer per line indicating the maximum number of bricks.
Sample Input
1
5 4
#.#.
...#
#..#
#...
##.#
Sample Output
2
