/* When all else is lost the future still remains. *//* You can be the greatest */#define rep(X,Y,Z) for(int X=(Y);X<(Z);X++)#define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--)#define fi first#define se second#define mk(X,Y) make_pair((X),(Y))#define inf 0x3f3f3f3f#define clr(X,Y) memset(X,Y,sizeof(X))#define pb push_back//head#include <iostream>#include <stdio.h>#include <queue>#include <algorithm>#include <string>#include <map>#include <string.h>using namespace std;#define maxN 15#define maxM 15int dx[] = {-1,0,1,0};int dy[] = {0,-1,0,1};int val[2][maxN][maxM];int mark[2][maxN][maxM];bool mp[maxN][maxM];int n , m;int check_val(int,int);int check_val(int n , int m){    int ans = 0;    rep(i,1,n+1) rep(j,1,m+1){        if(mp[i][j]){            ans = max(ans,min(val[1][i][j],val[0][i][j]));        }    }    return ans;}int dfs(int x , int y , int cnt){    queue<pair<int,int> > Q;    val[cnt][x][y] = 0;    mark[cnt][x][y] = 1;    Q.push(mk(x,y));    while(!Q.empty()){        int nx = Q.front().fi;        int ny = Q.front().se;        Q.pop();        rep(i,0,4){            int tx = nx + dx[i];            int ty = ny + dy[i];            if(!mp[tx][ty]) continue;            if(mark[cnt][tx][ty]) continue;            val[cnt][tx][ty] = val[cnt][nx][ny] + 1;            mark[cnt][tx][ty] = 1;            Q.push(mk(tx,ty));        }    }    if(cnt == 1) return check_val(n,m);    int ans = inf;    rep(i,x,n+1){        int t = (i == x) ? (y) : 1;        rep(j,t,m+1){            if(mp[i][j]){                rep(k,1,n+1) rep(l,1,m+1) mark[1][k][l] = 0;                rep(k,1,n+1) rep(l,1,m+1) val[1][k][l] = inf;                ans = min(ans,dfs(i,j,1));                            }        }    }    return ans;}int main(){    int T;    while(~scanf("%d",&T)) rep(ca,1,T+1){        clr(mp,0);        scanf("%d %d\n",&n,&m);        char t;        rep(i,1,n+1) {            rep(j,1,m+1){                scanf("%c",&t);                mp[i][j] = (t == ‘.‘) ? 0 : 1;            }            getchar();        }                int ans = inf;        rep(i,1,n+1) rep(j,1,m+1){            if(mp[i][j]){                clr(val,inf);                clr(mark,0);                ans = min(ans,dfs(i,j,0));            }        }        printf("Case %d: %d\n",ca,(ans>=inf)?-1:ans);    }    return 0;}

 1 /* When all else is lost the future still remains. */ 2 /* You can be the greatest */ 3 #define rep(X,Y,Z) for(int X=(Y);X<(Z);X++) 4 #define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--) 5 #define fi first 6 #define se second 7 #define mk(X,Y) make_pair((X),(Y)) 8 #define inf 0x3f3f3f3f 9 #define clr(X,Y) memset(X,Y,sizeof(X))10 #define pb push_back11 //head12 #include <iostream>13 #include <stdio.h>14 #include <queue>15 #include <algorithm>16 #include <string>17 #include <map>18 #include <string.h>19 using namespace std;20 #define maxN 2021 #define maxM 2022 int dx[] = {-1,0,1,0};23 int dy[] = {0,-1,0,1};24 int n , m;25 bool mp[maxN][maxM];26 int val[2][maxN][maxM];27 bool mark[2][maxN][maxM];28 void init(int cnt){29     rep(i,1,n+1) rep(j,1,m+1){30         val[cnt][i][j] = inf;31         mark[cnt][i][j] = 0;32     }33     return ;34 }35 int check_val(){36     int ans = 0;37     rep(i,1,n+1) rep(j,1,m+1){38         if(mp[i][j]) ans = max(ans,min(val[0][i][j],val[1][i][j]));39     }40     return ans;41 }42 void bfs(int x , int y , int cnt){43     queue<pair<int,int> > Q;44     Q.push(mk(x,y));45     mark[cnt][x][y] = 1;46     val[cnt][x][y] = 0;47     while(!Q.empty()){48         int nx = Q.front().fi;49         int ny = Q.front().se;50         Q.pop();51         rep(i,0,4){52             int tx = nx + dx[i];53             int ty = ny + dy[i];54             if(!mp[tx][ty]) continue;55             if(mark[cnt][tx][ty]) continue;56             val[cnt][tx][ty] = val[cnt][nx][ny] + 1;57             mark[cnt][tx][ty] = 1;58             Q.push(mk(tx,ty));59         }60     }61 }62 int main(){63 64     int T;65     scanf("%d",&T);66     rep(ca,1,T+1){67         int ans = inf;68         clr(mp,0);69         scanf("%d %d\n",&n,&m);70         char t;71         rep(i,1,n+1) {72             rep(j,1,m+1){73                 scanf("%c",&t);74                 mp[i][j] = (t == ‘.‘) ? 0 : 1;75             }76             getchar();77         }78         rep(rx,1,n+1) rep(ry,1,m+1){79             if(!mp[rx][ry]) continue;80             init(0); init(1);81             bfs(rx,ry,0);82             rep(ax,rx,n+1){83                 int t = (ax == rx) ? ry : 1;84                 rep(ay,t,m+1){85                     if(!mp[ax][ay]) continue;86                     init(1);87                     bfs(ax,ay,1);88                     ans = min(ans,check_val());89                 }90             }91         }92         printf("Case %d: %d\n",ca,(ans>=inf)?-1:ans);93 94     }95     return 0;96 }