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
#include <bits/stdc++.h>
using namespace std;
int n, cnt, res;
vector <int> sas[405];
int dist[405][405];
int vis[405];
string s;
void bfs(int v)
{
    ++cnt;
    queue <pair <int, int>> q;
    q.push({v, 0});
    while (!q.empty())
    {
        auto top = q.front();
        q.pop();
        if (vis[top.first] == cnt)
        {
            continue;
        }
        vis[top.first] = cnt;
        dist[v][top.first] = top.second;
        for (int i : sas[top.first])
        {
            if (vis[i] != cnt) q.push({i, top.second+1});
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        res = 1e9;
        cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            cin >> s;
            for (int j = 0; j < n; ++j)
            {
                if (s[j] == '1') sas[i].push_back(j+1);
            }
        }
        for (int i = 1; i <= n; ++i)
        {
            bfs(i);
        }
        for (int a = 1; a < n; ++a)
        {
            for (int b = a+1; b <= n; ++b)
            {
                int wyn = 0;
                for (int i = 1; i < n; ++i)
                {
                    for (int j = i+1; j <= n; ++j)
                    {
                        wyn = max(wyn, min(dist[i][j], min(dist[a][i], dist[a][j]) + min(dist[b][i], dist[b][j])));
                    }
                }
                res = min(res, wyn);
            }
        }
        cout << res << "\n";
        for (int i = 1; i <= n; ++i)
        {
            sas[i].clear();
        }
    }
}