黑洞2 (blackhole)

【题目描述】

小明有一个有 $n$ 行 $m$ 列的棋盘，一共有 $n\times m$ 个棋盘格子。

有一天他的棋盘被高维度生物入侵了，造出了若干个黑洞，第 $i$ 个黑洞位于棋盘的第 $x_i$ 行，第 $y_i$ 列，而其他格子都是正常的，每个格子上都放有一颗棋子。小明想到了一个有趣的游戏，他可以通过倾斜棋盘使得棋子发生一模一样的位移。具体来说，小明可以通过倾斜棋盘，使得棋盘上所有棋子同时往上下左右位移一个格子。

举个例子，当前棋子位于 $(i,j)$ ，小明设计了倾斜棋盘的按钮。

1. 按钮 U：它将移动到 $(i − 1, j)$
2. 按钮 D：它将移动到 $(i + 1, j)$
3. 按钮 L：它将移动到 $(i, j − 1)$
4. 按钮 R：它将移动到 $(i, j + 1)$

如果一颗棋子掉进黑洞里或掉出棋盘，那么该棋子将离开棋盘不再回来。

现在小明想知道，哪些棋子能成为最后的天选之棋子，即通过若干次操作后只有它仍然在棋盘上。

【输入格式】

多组数据。

第一行一个整数 $T$ ，表示数据组数。

对于每组数据，第一行两个整数 $n,m$ ,表示棋盘大小。

接下来 $n$ 行， 每行一个长度为 $m$ 的字符串，表示棋盘第 $i$ 行的状态，. 表示正常格子， O 表示黑洞。

【输出格式】

对于每组数据输出一行一个整数，表示能成为最后留下的棋子的数量。

【样例 $1$ 输入】

3
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.

【样例 $1$ 输出】

3
1
0

样例解释： 对于第一组数据，(1,4)可以通过RD成为留在棋盘上唯一一颗棋子，(1,5)可以通过D成为留在棋盘上唯一一颗棋子，（2,5）可以通过 U成为留在棋盘上唯一一颗棋子。一共3种可能。

【样例 $2$】

见下发文件

【子任务】

对于 $30\%$ 的数据 , $1\le n,m\le 4$ 。

对于 $70\%$ 的数据，$1\le n,m\le 15$。

对于$100\%$的数据，$1\le T\le 5,1\le n,m\le 40$。