问题 CH: Place the Robots

Robert是一位著名的工程师。一天，老板给了他一项任务，背景如下：他拿到一张由方块组成的地图。有三种方块：墙、草和空地。他的老板想在地图上放尽可能多的机器人。每个机器人都有一个激光武器，可以同时向四个方向（北、东、南、西）射击。机器人必须一直待在最初放置的方块区，并一直开火。激光束当然可以通过草地，但不能通过墙。机器人只能放在一个空块中。当然，老板不想看到一个机器人伤害另一个机器人。即除非两个机器人之间有一堵墙，否则不得将它们放在一条直线上（水平或垂直）。既然你是一个如此聪明的程序员，又是Robert最好的朋友之一，他请你帮他解决这个问题。即给定地图的描述，计算可以放置在地图中的机器人的最大数量。

第一行包含一个整数T(T≤50),它是测试样例的数量。
对于每个测试样例，第一行包含两个整数m和n(1 ≤ m,n ≤ 50),它们是映射的行和列大小。
接下来是m行，每行包含“#”、“*”或“o”构成的n个字符，分别表示墙、草和空地。

对于每个测试样例，首先在第一行中输出测试样例号，格式为“Case :”，其中，id是测试样例号，从1开始计算。在第二行中，输出可以放置在该地图中的机器人的最大数量。

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

Case :1
3
Case :2
5