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

int dx[] = {-1,0,0,1}, dy[] = {0,-1,1,0};

bool check(vector<vector<int>>& dist, int& r, int& C, int& k) {
    pair<int,int> a = {INT_MIN,0}, b = {INT_MAX,0}, c = {0,INT_MIN}, d = {0,INT_MAX};
    bool already_satisfied = true;
    for (int i=0; i<r; i++) {
        for (int j=0; j<C; j++) {
            if (dist[i][j]>k) {
                already_satisfied = false;
                if (i+j>a.first)
                    a = {i+j,i-j};
                if (i+j<b.first)
                    b = {i+j,i-j};
                if (i-j>c.second)
                    c = {i+j,i-j};
                if (i-j<d.second)
                    d = {i+j,i-j};
            }
        }
    }
    if (already_satisfied) return true;
    for (int i=0; i<r; i++) {
        for (int j=0; j<C; j++) {
            if (dist[i][j]>0) {
                int parm1 = max(abs(i+j-a.first),abs(i-j-a.second));
                int parm2 = max(abs(i+j-b.first),abs(i-j-c.second));
                int parm3 = max(abs(i+j-c.first),abs(i-j-b.second));
                int parm4 = max(abs(i+j-d.first),abs(i-j-d.second));
                if (max(max(parm1,parm2),max(parm3,parm4))<=k)
                    return true;
            }
        }
    }
    return false;
}

int solve() {
    int r,c;
    cin>>r>>c;
    vector<vector<int>> dist(r,vector<int>(c,-1));
    string s;
    queue<pair<int,int>> _bfs;
    for (int i=0; i<r; i++) {
        cin>>s;
        for (int j=0; j<c; j++) {
            if (s[j]=='1') {
                dist[i][j] = 0;
                _bfs.push({i,j});
            }
        }
    }
    while (!_bfs.empty()) {
        pair<int,int> p = _bfs.front();
        _bfs.pop();
        int x = p.first, y = p.second;
        for (int k=0; k<4; k++) {
            int _x = x + dx[k], _y = y + dy[k];
            if (_x>=0 && _x<r && _y>=0 && _y<c && dist[_x][_y]<0) {
                dist[_x][_y] = 1 + dist[x][y];
                _bfs.push({_x,_y});
            }
        }
    }
    int lo = 0, hi = r+c-2, mi;
    while (lo<hi) {
        mi = (lo+hi)/2;
        if (check(dist,r,c,mi))
            hi = mi;
        else lo = mi + 1;
    }
    return lo;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    for (int i=1;i<=t;i++) {
        cout<<"Case #"<<i<<": "<<solve()<<"\n";
    }
}