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

void solve(int n){
    vector<vector<int>> dist(n,vector<int>(n,1e9));

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            char c;
            cin >> c;
            if(c=='1')dist[i][j] = 1;
        }
    }

    for(int i = 0; i < n; i++) dist[i][i] = 0;

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i==k || i==j || j==k)continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int ans = 1e9;
    for(int a = 0; a < n; a++){
        for(int b = a+1; b < n; b++){
            int sr = 0;
            for(int i = 0; i < n; i++){
                for(int j = i+1; j < n; j++){
                    sr = max(sr,min(dist[i][j],min(dist[i][a]+dist[b][j],dist[i][b]+dist[a][j])));
                }
            }
            ans = min(ans, sr);
        }
    }
    cout<<ans<<endl;

}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin>>t;
    while(t--){
    int n;
    cin>>n;
        solve(n);
    }

    return 0;
}