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
#include <bits/stdc++.h>
using namespace std;

const int INF = 10000;

void floyd_warshall(vector<vector<int>>& dist, int n){
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int find_max_distance(const vector<vector<int>>& dist, int n){
    int max_dist = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            max_dist = max(max_dist, dist[i][j]);
        }
    }
    return max_dist;
}

int solve(vector<string>& graph, int n){
    vector<vector<int>> dist(n, vector<int>(n, INF));
    int count_0 = 0;
    
    for(int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            if(i == j) dist[i][j] = 0;
            else if(graph[i][j] == '1') dist[i][j] = 1;
            else count_0++;
        }
    }
    if(count_0 == 0) return 1;
    floyd_warshall(dist, n);
    
    int diameter = find_max_distance(dist, n);
    int min_diameter = diameter;
    
    for(int u = 0; u < n; u++){
        for(int v = u + 1; v < n; v++){
            if(dist[u][v] > 1){
                vector<vector<int>> new_dist = dist;
                
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        new_dist[i][j] = min(new_dist[i][j], min(new_dist[i][u] + new_dist[v][j], new_dist[i][v] + new_dist[u][j]));
                    }
                }
                
                diameter = find_max_distance(new_dist, n);
                min_diameter = min(min_diameter, diameter);
            }
        }
    }
    
    return min_diameter;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<string> graph(n);
        for (int i = 0; i < n; i++) {
            cin >> graph[i];
        }
        cout << solve(graph, n) << "\n";
    }
    
    return 0;
}