Problem Description
“纷纷世事无穷尽,天数茫茫不可逃。鼎足三分已成梦,后人凭吊空牢骚。”
三国的各种传奇故事被千百年传诵,为人们津津乐道。魏、蜀、吴三个势力相互制约,同时也相互利用,“三”的神奇和精妙尽在其中。于是,这个问题也是关于“三”的。
在一个N * M的地图上,两个点(x1, y1)和(x2, y2)之间的距离被定义成曼哈顿距离,魏、蜀、吴三个势力要在这个地图上分别选择自己的据点。由于地图上某些点已经被其他势力占据,为了避免不必要的冲突,他们希望自己的据点与其他被占据的点都可以保持一定的距离,包括他们三个势力据点的相互距离,也要满足约束。
现在,三个势力不可思议的开了一次首脑峰会,商谈据点的安排问题。你,作为一个像鲁肃大师一样爱好和平的外交家,要给出最大的限制距离,使得至少有一种安排方案满足条件。
Input
输入第一行为T,表示有T组测试数据。
每组数据以两个整数N和M开始,表示地图的规模。接下来的N行,每一行包含一个长度为M的字符串,表示地图,‘.’表示空地,’F’表示这里已被其他势力占据。地图至少有三个空格以供选择。
[Technical Specification]
1. 1 <= T <= 74
2. 1 <= N, M <= 74
Output
对每组数据,先输出为第几组数据,然后输出最大限制距离。
Sample Input
2
4 4
F...
....
....
....
4 4
F..F
....
....
F..F
Sample Output
Case 1: 3
Case 2: 1