#include<bits/stdc++.h>
using namespace std;

int main(){
        int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
        int tt;cin>>tt;
        for(int t=1;t<=tt;t++){
                int r,c;cin>>r>>c;
                vector<string> initial;
                for(int i=0;i<r;i++){
                        string row;cin>>row;
                        initial.push_back(row);
                }
                vector<vector<int> > dist;
                queue<pair<int,int> > q;
                for(int i=0;i<r;i++){
                        vector<int> row;
                        for(int j=0;j<c;j++){
                                if(initial[i][j]=='1'){
                                        row.push_back(0);
                                        q.push(make_pair(i,j));
                                }else row.push_back(INT_MAX);
                        }
                        dist.push_back(row);
                }
                int max_dist=0;
                while(!q.empty()){
                        int x = q.front().first,y = q.front().second;
                        q.pop();
                        max_dist = max(max_dist,dist[x][y]);
                        for(int i=0;i<4;i++){
                                int xx = x+dx[i],yy = y+dy[i];
                                if(xx>=0 && xx<r && yy>=0 && yy<c){
                                        if(dist[xx][yy]>dist[x][y]+1){
                                                dist[xx][yy] = dist[x][y]+1;
                                                q.push(make_pair(xx,yy));
                                        }
                                }
                        }
                }
                int lower=-1,upper=max_dist;
                while(upper-lower>1){
                        int mid = (upper+lower)/2;
                        int ipjmax=-r-c-1,ipjmin=r+c+1,imjmax=-r-c-1,imjmin=r+c+1;
                        for(int i=0;i<r;i++){
                                for(int j=0;j<c;j++){
                                        if(dist[i][j]>mid){
                                                ipjmin = min(i+j,ipjmin);
                                                ipjmax = max(i+j,ipjmax);
                                                imjmin = min(i-j,imjmin);
                                                imjmax = max(i-j,imjmax);
                                        }
                                }
                        }
                        if(ipjmax-ipjmin<=2*mid && imjmax-imjmin<2*mid
                        	|| ipjmax-ipjmin<2*mid && imjmax-imjmin<=2*mid
                        	|| ipjmax-ipjmin==2*mid && imjmax-imjmin==2*mid && (ipjmax + imjmax) % 2 == 0) {
                        	upper = mid;
                        }
                        else lower = mid;
                }
                cout<<"Case #"<<t<<": "<<upper<<endl;
        }
        return 0;
}