1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
#define ll long long
#define llu long long unsigned
#define ld long double
#define fr(i,n) for(int i=0;i<n;i++)
#define watch(x) cout<<(#x)<<"=="<<(x)<<endl
#define ft first
#define sc second
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define P 1000000007llu
#define N 405
#define LC 262144
using namespace std;
 
int getchar_pos_int() {
    int n=0, c=getchar();
    while('0'<=c&&c<='9') {n=n*10+c-'0'; c=getchar();}
    return n;
}
 
int adj[N][N], p[N][N];
ll dist[N][N];
list<int> shortestPath[N][N];
int n;

list<int> retrievePath(int i, int j) {
    list<int> path;
    if(p[i][j]==-1) {
        if(i==j) path.pb(i);
        return path;
    }
    path=retrievePath(i,p[i][j]);
    path.pb(p[i][j]);
    path.splice(path.end(),retrievePath(p[i][j],j));
    return path;
}
         
void shortestPathsFW() {
    fr(i,n) {
        fr(j,n) {
            if(adj[i][j]<INT32_MAX){
                dist[i][j]=(ll)adj[i][j];
            } else if(i!=j) dist[i][j]=INT64_MAX;
        }
    }
    fr(k,n) {
        fr(i,n) {
            fr(j,n) {
                if(dist[i][k]<INT64_MAX&&dist[k][j]<INT64_MAX) {
                    if(dist[i][j]>dist[i][k]+dist[k][j]) {
                        p[i][j]=k, dist[i][j]=dist[i][k]+dist[k][j];
                    }
                }
            }
        }
    }
    fr(i,n) fr(j,i) shortestPath[i][j]=shortestPath[j][i]=retrievePath(i,j);
}



int binsearchMinimum() {
    int l=1,r=n,m;
    while(l<r) {
        m=(l+r)/2;
        set<pii> edgesOnPath, s2;
        bool flag=false, somePathAlreadyIn=false; 
        fr(i,n) fr(j,n) {
            if(i==j) continue;
            if(dist[i][j]-m>1) {
                l=m+1; i=n; flag=true; break;
            }
            if(dist[i][j]-m==1) {
                if(!somePathAlreadyIn) {
                    for(auto it=shortestPath[i][j].begin();next(it)!=shortestPath[i][j].end();it++) {
                        edgesOnPath.insert({*it,*next(it)});
                    }
                    somePathAlreadyIn=true;
                } else {
                    for(auto it=shortestPath[i][j].begin();next(it)!=shortestPath[i][j].end();it++) {
                        if(edgesOnPath.find({*it,*next(it)})!=edgesOnPath.end()) {
                            s2.insert({*it,*next(it)});
                        }
                    }
                    edgesOnPath=s2;s2.clear();
                    if(edgesOnPath.empty()) {
                        l=m+1; i=n; flag=true; break;
                    }
                }
            } 
        }
        if(!flag) r=m;
    }
    return m;
}
 
string s;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t; cin>>t;
    while(t--) {
        cin>>n;
        fr(i,n) {
            fr(j,n) {
                if(i==j) adj[i][j]=0,p[i][j]=i;
                else adj[i][j]=INT32_MAX,p[i][j]=-1;
            }
        }
        fr(i,n) {
            cin>>s; 
            fr(j,n) {
                if(s[j]=='1') adj[i][j]=adj[j][i]=1;
                else adj[i][j]=adj[j][i]=INT32_MAX;
            }
        }
        shortestPathsFW();
        cout<<binsearchMinimum()<<'\n';
    }
    return 0;
}