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

#define all(a) begin(a), end(a)
using ll = long long;

vector<int> BFS(vector<vector<int>> const &adj, int st) {
    queue<int> q;
    int n = adj.size();
    vector<int> dist(n, -1);
    auto push = [&](int u, int d) {
        if (dist[u] != -1)
            return;

        dist[u] = d;
        q.push(u);
    };

    push(st, 0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        int d = dist[u];
        for (int v = 0; v < n; v++)
            if (adj[u][v])
                push(v, d + 1);
    }
    return dist;
}

// < mx
pair<vector<int>, vector<int>> count_sort(vector<pair<int, int>> const &arr, int mx) {
    vector<int> ptr(mx + 1), a(arr.size());
    for (auto [k, v] : arr)
        ++ptr[k + 1];

    partial_sum(all(ptr), begin(ptr));
    for (auto [k, v] : arr)
        a[ptr[k]++] = v;

    for (int i = ptr.size() - 1; i > 0; i--)
        ptr[i] = ptr[i - 1];
    ptr[0] = 0;
    return {a, ptr};
}

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n, vector<int>(n));
    for (auto &i : adj)
        for (auto &j : i) {
            char c;
            cin >> c;
            j = c - '0';
        }

    vector<vector<int>> dist(n);
    for (int i = 0; i < n; i++)
        dist[i] = BFS(adj, i);

    vector<vector<int>> res(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        vector<vector<int>> layer(n);
        for (int j = 0; j < n; j++)
            layer[dist[i][j]].push_back(j);

        for (int u = 0; u < n; u++) {
            auto const &d1 = dist[i], d2 = dist[u];
            // min(d1[x], d2[x] + f)
            int cap = 0, cur = n - 1;
            const int mx = d1[u] + 1;

            vector<int> cnt(n);
            vector<int> ptr(mx + 1);

            for (int j = 0; j < n; j++) {
                int l = d1[j] - d2[j];
                if (l <= 0)
                    cap = max(cap, d1[j]);
                else {
                    ++cnt[d2[j]];
                    if (l < mx)
                        ++ptr[l + 1];
                }
            }
            partial_sum(all(ptr), begin(ptr));
            vector<int> srt(ptr.back());

            for (int j = 0; j < n; j++) {
                int l = d1[j] - d2[j];
                if (l > 0 && l < mx)
                    srt[ptr[l]++] = d2[j];
            }

            for (int j = mx; j > 0; j--)
                ptr[j] = ptr[j - 1];
            ptr[0] = 0;

            auto get_result = [&](int t) {
                while (cur >= 0 && !cnt[cur])
                    --cur;

                if (cur >= 0)
                    return cur + t;
                return 0;
            };

            for (int t = 0; t < mx; t++) {
                cap = max(cap, get_result(t));
                for (auto v : layer[t])
                    res[u][v] = max(res[u][v], cap);

                for (int j = ptr[t]; j < ptr[t + 1]; j++)
                    --cnt[srt[j]];
            }
        }
    }

    int ans = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = min(ans, max(res[i][j], res[j][i]));

    cout << ans << "\n";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int tests = 1;
    cin >> tests;

    while (tests--)
        solve();
}