当前没有测试数据。

罗伯特是一位著名的工程师。有一天，他的老板给他下达了一项任务。任务的背景如下：

给定一个由正方形块组成的地图。有三种方块：墙、草和空。他的老板想在地图上放置尽可能多的机器人。每个机器人都拿着一把激光武器，可以同时向四个方向（北、东、南、西）射击。机器人必须一直停留在最初放置它的方块上，并一直开火。激光束当然可以穿过格拉斯的网格，但不能穿过沃尔的网格。机器人只能放置在空块中。当然，老板不希望看到一个机器人伤害另一个机器人。换句话说，两个机器人不能放在一条线上（水平或垂直），除非它们之间有一堵墙。

现在你是一个如此聪明的程序员，也是罗伯特最好的朋友之一，他要求你帮助他解决这个问题。也就是说，给定地图的描述，计算可放置在地图中的最大机器人数量。

输入

第一行包含一个整数 T （<= 11），它是测试用例的数量。

对于每个测试用例，第一行包含两个整数 m 和 n （1<= m， n <=50），它们是映射的行和列大小。然后是 m 行，每行包含 n 个字符 '#'、'*' 或 'o'，分别代表 Wall、Grass 和 Empty。

输出

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

Place the Robots ZOJ - 1654