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
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using namespace std;
const int maxn = 405;
vector<int> V[maxn];
vector<int> topo[maxn];
vector<pi> dystp[maxn];
void solve(){
    int n;
    cin>>n;
    int dyst[n + 1][n + 1],odp[n + 1][n + 1],kol[n + 1][n + 1];
    FOR(i,0,n + 1){
        FOR(j,0,n + 1){
            dyst[i][j] = 0;
            odp[i][j] = 0;
            kol[i][j] = 0;
        }
    }
    FOR(i,1,n + 1){
        string W;
        cin>>W;
        FOR(j,1,n + 1){
            if(W[j - 1] == '1'){
                V[i].pb(j);
            }
        }
    }
    FOR(i,1,n + 1){
        int vis[n + 2];
        FOR(j,0,n + 1){vis[j] = 0;}
        queue<int> Q;
        Q.push(i);
        topo[i].pb(i);
        vis[i] = 1;
        while(!Q.empty()){
            auto x = Q.front();
            Q.pop();
            for(auto y : V[x]){
                if(vis[y] == 0){
                    vis[y] = 1;
                    dyst[i][y] = dyst[i][x] + 1;
                    topo[i].pb(y);
                    kol[i][y] = topo[i].size();
                    dystp[i].pb({dyst[i][y],y});
                    Q.push(y);
                }
            }
        }
        sort(dystp[i].begin(),dystp[i].end());
    }
    int tablica[n + 1];
    FOR(i,1,n + 1){ //dla kazdego skierowania
        vector<int> nowy = topo[i];
        FOR(j,0,n){ //dla kazdego wierzcholka
            FOR(k,0,n + 1){
                tablica[k] = 0;
            }
            FOR(k,0,n){
                if(k == j){continue;}
                tablica[dyst[nowy[k]][nowy[j]]] = max(tablica[dyst[nowy[k]][nowy[j]]],dyst[nowy[k]][i]);     
            }
            vector<pi> V1;
            int maxi = 0;
            for(int k = n - 1; k >= 0;--k){
                if(tablica[k] > maxi){
                    maxi = tablica[k];
                    V1.pb({k,tablica[k]});
                }
            }
            int poc = 0;
            int aktualny = topo[i][j];
            FOR(k,0,dystp[i].size()){
                int w1 = dystp[i][k].s;
                if(kol[i][w1] > kol[i][aktualny]){continue;}
                while(poc + 1 < V1.size() && min(V1[poc].s, V1[poc].f + dystp[i][k].f) <= min(V1[poc + 1].s,V1[poc + 1].f + dystp[i][k].f)){
                    ++poc;
                }
                int p1 = min(dystp[i][k].s,aktualny);
                int p2 = max(dystp[i][k].s,aktualny);
                odp[p1][p2] = max(odp[p1][p2],min(V1[poc].s, V1[poc].f + dystp[i][k].f));
            } 
        }
    }
    FOR(i,1,n + 1){
        V[i].clear();
        topo[i].clear();
        dystp[i].clear();
    }
    int wyn = 1e9;
    FOR(i,1,n + 1){
        FOR(j,i + 1,n + 1){
            wyn = min(wyn,odp[i][j]); 
        }
    }
    cout<<wyn <<"\n";
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    FOR(i,0,t){
        solve();
    }
}