题目描述

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

要在空地上放能向上下左右$\red {4}$个方向发射激光的机器人。

墙壁能挡住激光，草地不能挡住激光也不能放机器人。

在机器人不能互相打到对方的情况下，最多放置多少个机器人。

输入格式

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

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

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

$\red {‘\#’}$代表墙壁，$\red {‘*’}$代表草地，$\red {‘o’}$代表空地。

输出格式

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

第二行包含一个整数，表示机器人的个数。

样例

输入样例

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

输出样例

Case :1
3
Case :2
5

提示

$\red {1≤m,n≤50}$