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