1 #include<cstdio>
 2 const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0},M=60,N=3600;
 3 int cnt,num,b[M][M],d[N],q[N],v[N<<1],hea[N],nex[N<<1];
 4 bool f,a[M][M],c[N][N],vis[N];
 5 char s[M];
 6 
 7 void sd(int x,int y)
 8 {
 9     b[x][y]=cnt;
10     for (int i=0,u,v;i<4;++i)
11         if (b[u=x+dx[i]][v=y+dy[i]]==0 && a[u][v]==a[x][y]) sd(u,v);
12 }
13 
14 void add(int x,int y) { v[++num]=y,nex[num]=hea[x],hea[x]=num; }
15 
16 int dep(int x)
17 {
18     int l=0,r=1,y,i; 
19     for (vis[q[1]=x]=f,d[x]=0;l^r;)
20         for (i=hea[x=q[++l]];i;i=nex[i])
21             if (vis[y=v[i]]^f) vis[q[++r]=y]=f,d[y]=d[x]+1;
22     return d[q[r]];
23 }
24 
25 int main()
26 {
27     int T,n,m,i,j,k,x,y,u,v;
28     for (scanf("%d",&T);T;--T)
29     {
30         scanf("%d%d",&n,&m);
31         for (i=1;i<=n;++i)
32             for (scanf("%s",s),j=1;j<=m;++j)
33                 if (s[j-1]==‘O‘) a[i][j]=1; else a[i][j]=0;
34         for (i=cnt=num=0;i<n+2;++i) b[i][0]=b[i][m+1]=-1;
35         for (i=0;i<m+2;++i) b[0][i]=b[n+1][i]=-1;
36         for (i=1;i<=n;++i)
37             for (j=1;j<=m;++j) b[i][j]=0;
38         for (i=1;i<=n;++i)
39             for (j=1;j<=m;++j)
40                 if (!b[i][j]) ++cnt,sd(i,j);
41         for (i=1;i<=cnt;++i)
42             for (j=1;j<=cnt;++j) c[i][j]=1;
43         for (i=1;i<=cnt;++i) hea[i]=0;
44         for (i=1;i<=n;++i)
45             for (j=1;j<=m;++j)
46                 for (u=b[i][j],k=2;k<4;++k)
47                     if (~(v=b[x=i+dx[k]][y=j+dy[k]]) && c[u][v] && u^v)
48                         add(u,v),add(v,u),c[u][v]=c[v][u]=0;
49         for (i=1;i<=cnt;++i) vis[i]=f;
50         for (y=cnt,i=1;i<=cnt;++i)
51             if (f=!f,(x=dep(i))<y) y=x;
52         printf("%d\n",y);
53     }
54     return 0;
55 }