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
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int SIZE=404;
int FW[SIZE][SIZE];

void RESET(int N){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i!=j){
                FW[i][j]=inf;
                FW[j][i]=inf;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T,N;
    char Z;
    cin>>T;

    while(T--){

    cin>>N;

    RESET(N);

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>Z;
            if(Z=='0'){continue;}
            FW[i][j]=1;
            FW[j][i]=1;
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int h=1;h<=N;h++){
                FW[j][h]=min(FW[j][h],FW[j][i]+FW[i][h]);
                FW[h][j]=FW[j][h];
            }
        }
    }
    int MIN,MAX=0;
    for(int a=1;a<=N;a++){
        for(int b=1;b<=N;b++){
            MAX=max(MAX,FW[a][b]);
            //cout<< FW[a][b]<<' ';
        }//cout<<'\n';
    }
    MIN=MAX;

    for(int a=1;a<=N;a++){
        for(int b=1;b<=N;b++){
            if(a==b) continue;
            MAX=0;
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    MAX=max(MAX,min(FW[i][j],min(FW[i][a]+FW[b][j],FW[i][b]+FW[a][j])));
                }
            }
            MIN=min(MIN,MAX);
        }
    }
    cout<<MIN<<'\n';

    }


return 0;}