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
#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9;

void floyd_warshall(std::vector<std::vector<int>>& distance, int n) { // https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (distance[i][k] < INF && distance[k][j] < INF) {
                    distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);

    while (t) {
        int n;
        scanf("%d", &n);

        std::vector<std::vector<int>> distance(n, std::vector<int>(n, INF));

        for (int i = 0; i < n; i++) {
            std::string row;
            std::cin >> row;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    distance[i][j] = 0;
                } else if (row[j] == '1') {
                    distance[i][j] = 1;
                }
            }
        }

        floyd_warshall(distance, n);

        int org_srednica = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                org_srednica = std::max(org_srednica, distance[i][j]);
            }
        }

        int best_srednica = org_srednica;
        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                if (distance[u][v] > 1) {
                    std::vector<std::vector<int>> new_distance = distance;

                    for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                            new_distance[i][j] = std::min(new_distance[i][j], std::min(new_distance[i][u] + new_distance[v][j], new_distance[i][v] + new_distance[u][j]));
                        }
                    }

                    int new_srednica = 0;
                    for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                            new_srednica = std::max(new_srednica, new_distance[i][j]);
                        }
                    }

                    best_srednica = std::min(best_srednica, new_srednica);
                }
            }
        }
        printf("%d\n", best_srednica);
        t--;
    }

    return 0;
}