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

using namespace std;

constexpr int nax = 400;

short n;
short dist[nax][nax];
short diff[nax][nax][nax];
short pref_max[nax][nax][nax];
short suf_max[nax][nax][nax];
short farthest[nax];
short order[nax][nax];

short idxuvi[nax][nax][nax];
short bucket_sz[2 * nax + 1];
short bucket[2 * nax + 1][nax];

short farthest_with_tel(int u, int v, int i) {
    int idx = idxuvi[u][v][i];

    if (idx == n) {
        return dist[i][order[i][n - 1]];    
    } else if (idx == 0) {
        return dist[i][u] + dist[i][order[v][n - 1]];
    } else {
        return max(pref_max[i][v][idx - 1], (short) (dist[i][u] + suf_max[i][v][idx])); 
    }
}

short score(int u, int v) {
    short maks = 0;

    for (int i = 0; i < n; ++i) {
        maks = max(maks, min(farthest_with_tel(u, v, i), farthest_with_tel(v, u, i)));
    }

    return maks;
}

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                char c;
                cin >> c;
                dist[i][j] = c == '1' ? 1 : n;                
            }
            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) {
                    dist[i][j] = min((int) dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            iota(order[i], order[i] + n, 0);
            sort(order[i], order[i] + n, [&](int u, int v) { return dist[i][u] < dist[i][v]; });
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                fill(bucket_sz, bucket_sz + 2 * n, 0);
                for (int k = 0; k < n; ++k) {
                    int idx = dist[i][k] - dist[j][k] + n;
                    bucket[idx][bucket_sz[idx]++] = k;
                }
                int diff_idx = 0;
                for (int idx = 0; idx <= 2 * n; ++idx) {
                    for (int k = 0; k < bucket_sz[idx]; ++k) {
                        diff[i][j][diff_idx++] = bucket[idx][k];
                    }
                }

                pref_max[i][j][0] = dist[i][diff[i][j][0]];
                for (int k = 1; k < n; ++k) {
                    pref_max[i][j][k] = max(pref_max[i][j][k - 1], dist[i][diff[i][j][k]]); 
                }

                suf_max[i][j][n - 1] = dist[j][diff[i][j][n - 1]];
                for (int k = n - 2; k >= 0; --k) {
                    suf_max[i][j][k] = max(suf_max[i][j][k + 1], dist[j][diff[i][j][k]]);
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int v = 0; v < n; ++v) {
                int idx = 0;

                for (int k = 0; k < n; ++k) {
                    int u = order[i][k];
                    while (idx < n and dist[i][diff[i][v][idx]] - dist[v][diff[i][v][idx]] < dist[i][u]) {
                        ++idx;
                    }
                    idxuvi[u][v][i] = idx;
                }
            }
        }

        short res = n;
        for (int u = 0; u < n; ++u) {
            for (int v = u + 1; v < n; ++v) {
                res = min(res, score(u, v));
            }
        }

        cout << res << "\n";
    }
}