题目描述

给出一个地图（网格），格子分为空地，草地，墙壁。

• 要在空地上放能向上下左右 $4$ 个方向发射激光的机器人。
• 墙壁能挡住激光，草地不能挡住激光也不能放机器人。
• 在机器人不能互相打到对方的情况下，最多放置多少个机器人。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $m$ 和 $n$，表示地图的大小为 $m$ 行 $n$ 列。

接下来 $m$ 行，每行包含 $n$ 个字符，用来描述整个地图。

• # 代表墙壁
• * 代表草地
• o 代表空地

输出格式

每组测试数据在第一行输出 Case :id，id 是数据编号，从 $1$ 开始。

第二行包含一个整数，表示最多能放置的机器人个数。

样例

输入样例：

2
4 4
o***
*###
oo#o
***o
4 4
#ooo
o#oo
oo#o
***#

输出样例：

Case :1
3
Case :2
5

样例解释

Case 1 地图：

o * * *
* # # #
o o # o
* * * o

一种放置方案（在 o 处放机器人，使得它们不会相互攻击到）： 第1行第1列，第3行第1列，第3行第4列。
最多放3个。

Case 2 地图：

# o o o
o # o o
o o # o
* * * #

一种放置方案：放置多个机器人在空地上，最多5个。

数据范围

• $1 \le T$（未给出具体上限，但数据量不大）
• $1 \le m, n \le 50$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB