Sheldon and Penny are neighbours. Penny really likes grid games so Sheldon develops a new grid based game for Penny. The game consists of a M×N grid (M rows, N columns) and an infinite number of black and white knights. The grid has some open and some closed blocks. In the beginning of the game each player chooses his colour of knight. The rule says that each player on his turn can place his knight on any of the open blocks such that none of his knights attack any knight of other colour (he may attack any knight of the same colour). You are given a M×N grid. Specify the maximum number of knights (black and white) which can be placed on the grid. The game stops when any one player cannot place any more knights.

Note: In one turn, Knight can move exactly two squares horizontally and one square vertically, or two squares vertically and one square horizontally.

Input

First line specifies T, the number of test cases.

First line of each test case gives M and N separated by a single space

This is followed by a grid of size M×N consisting of ‘.’ And ‘#’. Each ‘.’ represents an open position and each ‘#’ represents closed position.

Output

Output 1 line for each test case giving the maximum possible value of knights that can be placed.

Constraints

1 <= T <= 5
1 <= M, N <= 10
0 <= Number of open positions "." <= 10

Example

Input:
2
3 3
...
...
...
3 3
...
.#.
...

Output:
7
6