미니언들의 벽돌 벽 쌓기

그루의 연구실 벽 하나가 폭발로 무너져서 미니언들이 다시 쌓아야 한다. 벽의 높이는 $H$칸, 너비는 $W$칸이다.

벽돌 하나는 정확히 두 칸을 덮는다. 가로 벽돌은 같은 행에서 옆으로 붙은 두 칸을 덮고, 세로 벽돌은 같은 열에서 위아래로 붙은 두 칸을 덮는다. 벽에는 금지 칸이 있어서 어떤 벽돌도 그 칸을 덮을 수 없다. 벽돌끼리 겹칠 수 없고, 벽돌이 덮는 두 칸은 모두 벽 안에 있어야 한다.

미니언들은 금지되지 않은 칸을 최대한 많이 덮으려 한다. 전부 덮는 것이 늘 가능하지는 않으므로 몇 칸은 비워 둘 수 있다.

벽은 $W$개의 문자로 이루어진 $H$개의 행으로 주어진다. 문자 X는 금지 칸을, 문자 O는 벽돌이 덮어도 되는 칸을 뜻한다.

각 벽마다 비워 두는 칸을 최소 몇 개까지 줄일 수 있는지 구하라.

그림 1: 금지 칸을 어둡게 칠한 예시 벽 (a)와 (c), 그리고 가능한 벽돌 배치 (b), (d), (e). 덮이지 않은 칸은 빗금으로 표시했다. (c)의 벽은 모든 칸을 덮을 수 없고, (d)와 (e)는 두 칸만 비워 두는 최적 배치다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스의 첫 줄에는 벽의 높이 $H$와 너비 $W$가 주어진다. ($1 \le H, W \le 100$)

이어지는 $H$개의 줄에는 각각 $W$개의 문자가 주어진다. 각 문자는 X 또는 O이다.

각 테스트 케이스마다 한 줄에, O로 표시된 칸을 최대한 많이 덮도록 벽돌을 놓았을 때 덮이지 않고 남는 칸의 최소 개수를 출력한다.