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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e6;

int t;
int n;
int G[403][403];
int dist[403][403];
int res = INF;

std::pair<int, int> local_max;

void run_test_cases();
void read_test_case();
void floyd_warshall();
void reset_variables();
void solve_test_case();
void find_max();
void print_result();
void skip_every_pair();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    run_test_cases();
    return 0;
}

// OK
void run_test_cases() {
    cin >> t;
    for (int idx = 0; idx < t; ++idx) {
        read_test_case();
        solve_test_case();
        print_result();
        if (idx != t - 1) {
            reset_variables();
        }
    }
}

// OK
void solve_test_case() {
    floyd_warshall();
    // find_max();
    G[local_max.first][local_max.second] = 0;
    G[local_max.second][local_max.first] = 0;
    skip_every_pair();
}

void skip_every_pair() {
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int curr_max = 0;
            for (int u = 0; u < n; ++u) {
                for (int v = u + 1; v < n; ++v) {
                    curr_max = std::max(
                        curr_max,
                        std::min(dist[u][v], std::min(dist[u][i] + dist[j][v], dist[u][j] + dist[i][v]))
                    );
                }
            }
            // std::cout << i << " " << j << " " << curr_max << "\n";
            res = std::min(res, curr_max);
        }
    }
}

// OK
void read_test_case() {
    cin >> n;
    char input_buff;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> input_buff;
            G[i][j] = (input_buff == '1') ? 1 : INF;
        }
    }
}

// OK
void floyd_warshall() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dist[i][j] = G[i][j];
        }
    }
    
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
    }
    
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

// OK
void find_max() {
    int max_value = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] < INF && dist[i][j] > max_value) {
                max_value = dist[i][j];
                local_max = {i, j};
            }
        }
    }
    res = max_value;
}

// OK
void reset_variables() {
    res = INF;
    local_max = {0, 0};
    for (int i = 0; i < 403; ++i) {
        for (int j = 0; j < 403; ++j) {
            G[i][j] = 0;
            dist[i][j] = 0;
        }
    }
}

// OK
void print_result() {
    cout << res << "\n";
}