SP11405 DCEPC502 - Just Like the Good Old Days

谢尔顿和佩妮是邻居，佩妮对网格游戏情有独钟。为此，谢尔顿设计了一款全新的网格游戏供佩妮娱乐。游戏由一个 $M \times N$ 的网格构成（$M$ 行，$N$ 列），并包含无限数量的黑白骑士。网格中有些格子是开放的，有些则是封闭的。游戏开始时，每位玩家选择一种颜色的骑士。规则规定，每个玩家在自己的回合内，可以将骑士放置在任意一个开放的格子上，但要保证该骑士不会攻击到对方颜色的骑士（同色骑士之间可以相互攻击）。现给定一个 $M \times N$ 的网格，请计算出可以在其上放置的最大骑士总数（包括黑色和白色骑士）。当其中一位玩家无法再放置骑士时，游戏结束。 注意：骑士可以在一次移动中水平移动两格并垂直移动一格，或者垂直移动两格并水平移动一格。

第一行输入整数 $T$，表示测试用例的数量。 然后对于每个测试用例，第一行输入两个整数 $M$ 和 $N$，用空格分隔。 接下来是一个包含 $M \times N$ 个字符的网格，每个字符为 `.` 或 `#`。其中 `.` 表示开放位置，而 `#` 表示封闭位置。

对于每个测试用例，输出一行，表示可以放置的骑士最大数量。

- $1 \le T \le 10$ - $1 \le M, N \le 50$ **本翻译由 AI 自动生成**