The Minions Build a Brick Wall

Time limit1sMemory limit256 MB

Summary

Cover a grid with obstacles using dominoes to leave as few open cells bare as possible.

Level: Medium4 of 10
Topics: Graph, BFS, DFS
Solved: No attempts yet

Problem

A wall in Gru's laboratory collapsed in an explosion, so the minions have to rebuild it. The wall is $H$ squares high and $W$ squares wide.

One brick covers exactly two squares. A horizontal brick covers two squares side by side in the same row, and a vertical brick covers two squares stacked in the same column. Some squares of the wall are forbidden, and no brick may cover a forbidden square. Bricks must not overlap, and both squares of a brick have to lie inside the wall.

The minions want to cover as many of the squares that are not forbidden as they can. Covering all of them is not always possible, so some squares may be left bare.

The wall is given as $H$ rows of $W$ characters. The character X marks a forbidden square, and the character O marks a square that a brick may cover.

For each wall, find the smallest number of squares that stay bare.

Figure 1: sample walls (a) and (c) with forbidden squares shaded, and brick layouts (b), (d), and (e) with the uncovered squares hatched. The wall in (c) cannot be covered completely, and both (d) and (e) are optimal layouts that leave two squares bare.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 10$ )

The first line of each test case contains the height $H$ and the width $W$ of the wall. ( $1 \le H, W \le 100$ )

Each of the next $H$ lines contains $W$ characters. Every character is either X or O.

Output

For each test case, print one line with the smallest number of squares marked O that stay uncovered when the bricks cover as many of them as possible.

Examples2

Example 1

Input

1
6 6
OOOXOO
OOOOXO
XOXOOO
OXOOOO
OXOOOO
OOOXOX

Expected output

Example 2
Input
```
3
1 1
O
1 1
X
1 2
OO
```
Expected output
```
1
0
0
```