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
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
using namespace std;
const int inf = 1e9;



bool okay(int n, vector<vector<int>> &odl, int cel){

    vector<vector<int>> pomoc(n, vector<int>(n)); // Jeśli i to ten dalszy teleporter od j, to pomoc[i][j] oznacza najdalszą odległość w jakiej może być drugi teleporter od i.
    for(int i=0;i<n; i++){
        for(int j=0; j<n; j++){
            int najdalsza = 0;
            for(int k=0; k<n; k++){
                if(odl[j][k] > cel){
                    najdalsza = max(najdalsza, odl[i][k]);
                }
            }
            pomoc[i][j] = cel - najdalsza;
        }
    }
    for(int uno = 0; uno<n; uno++){
        for(int dos = 0; dos < n; dos++){
            bool dasie = 1;
            for(int i=0; i<n; i++){
                if(odl[i][uno] > cel && odl[i][dos]>cel) dasie=0;
                if(odl[i][uno]>=odl[i][dos]){
                    if(odl[i][dos] > pomoc[uno][i]){
                        dasie = 0;
                        break;
                    }
                }
                else{
                    if(odl[i][uno] > pomoc[dos][i]){
                        dasie =0;
                        break;
                    }
                }
            }
            if(dasie) return 1;
        }
    }
    return 0;
}


void solve(){
    int n;
    cin >> n;
    vector<vector<bool>> gra(n, vector<bool>(n));
    vector<vector<int>> odl(n, vector<int>(n, inf));
    string s;
    for(int i=0; i<n; i++){
        cin >> s;
        for(int j=0; j<n; j++){
            if(s[j]=='1'){
                gra[i][j]=1;
            }
        }
    }
    for(int i=0; i<n; i++){
        queue<int> bfs;
        odl[i][i]=0;
        bfs.push(i);
        while(!bfs.empty()){
            int aktu = bfs.front();
            bfs.pop();
            for(int j=0; j<n; j++){
                if(odl[i][j] == inf){
                    if(gra[aktu][j]){
                        odl[i][j] = odl[i][aktu]+1;
                        bfs.push(j);
                    }
                }
            }
        }
    }
    int l = 0, r = n;
    while(l<r){
        int m = (l+r)/2;
        if(okay(n, odl, m)){
            r = m;
        }
        else{
            l = m+1;
        }
    }
    cout << l << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}