ANGRYKN - Angry Knights

no tags 

Some angry knights want to settle on the checkmate board of n x m size. The angry knights are much like the ordinary ones, but each can move at any time. Moreover they don't like each other and won't allow any other knight on their territory. Luckily someone removed some cells from the board, so now more knights can settle on the board without bothering each other. Count the maximal number of angry knight that can live on the board simultaneously.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test starts with two numbers n and m - the dimensions of the board. Then n lines follow each consisting of m characters. Character 'x' means that the corresponding cell is removed, character '.' that it is present.

Constraints

1 <= t <= 100
2 <= n, m <= 100

Output

For each test print the maximal number of angry knights that can settle on such board.

Example

Input:
2
2 3
...
...
3 3
...
xxx
...

Output:
4
2


Added by:Spooky
Date:2009-11-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Advancement Autumn 2009, http://sevolymp.uuuq.com/, author: Alexey Shchepin