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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define piii pair<int, pair<int, int>>
#define st first
#define nd second.first
#define rd second.second
#define For(i, l, r) for (int i = l; i <= r; i++)
#define Forcin(l, r, a)          \
    for (int i = l; i <= r; i++) \
        cin >> a[i];
#define Ford(i, l, r) for (int i = l; i >= r; i--)
#define ben(v) v.begin(), v.end()
#define LOCAL 0
#define LOCAL2 0
using namespace std;

const int M = 400005, inf = 1e9;

bool comp(piii a, piii b)
{
    if (a.st != b.st)
        return a.st > b.st;
    return a.second < b.second;
}

void solve()
{
    int n;
    cin >> n;
    n++;
    vector<vector<bool>> adjacency_matrix(n, vector<bool>(n, 0));
    vector<vector<int>> graph(n);
    vector<vector<int>> distances(n);
    n--;
    For(i, 1, n)
    {
        string w;
        cin >> w;
        w = "#" + w;
        For(j, 1, n)
        {
            if (w[j] == '1')
            {
                graph[i].push_back(j);
                adjacency_matrix[i][j] = 1;
            }
        }
    }
    For(i, 1, n)
    {
        vector<int> distance(n + 1, inf);
        queue<pii> q;
        q.push({i, 0});
        while (!q.empty())
        {
            auto [v, d] = q.front();
            q.pop();
            if (d >= distance[v])
                continue;
            distance[v] = d;
            for (auto u : graph[v])
            {
                q.push({u, d + 1});
            }
        }
        distances[i] = distance;
    }
    vector<piii> dists;
    For(i, 1, n)
        For(j, i + 1, n)
            dists.push_back({distances[i][j], {i, j}});
    sort(ben(dists), comp);
    int best = 0, ac = 1;
    pii added = {0, 0};
    For(i, 1, n)
        For(j, i + 1, n)
            best = max(best, distances[i][j]);
    for (auto tel : dists)
    {
        auto [a, b] = tel.second;
        int maxi = 0;
        for (auto el : dists)
        {
            auto [u, v] = el.second;
            maxi = max(maxi, min(el.st, min(distances[a][u] + distances[b][v], distances[b][u] + distances[a][v])));
            if (maxi >= best)
                break;
        }
        if (maxi < best)
        {
            best = maxi;
            added = {a, b};
            ac = 1;
        }
    }
    cout << best << '\n';
}

signed main()
{
    cin.tie(0)->sync_with_stdio();
    if (LOCAL)
        freopen("moje/15.in", "r", stdin);
    if (LOCAL2)
        freopen("local_out.txt", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
}