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
// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;

_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
int T; cin>>T;
// int T=1;
while (T--) []{
    
    int n; cin>>n;
    
    mt19937 rnd(chrono::high_resolution_clock().now().time_since_epoch().count());
    
    vector<int> p(n); for (int i=0; i<n; ++i) p[i]=i;
    ranges::shuffle(p,rnd);
    vector g(n,vector<int>());
    for (int i=0; i<n; ++i) {
        string s; cin>>s;
        for (int j=0; j<n; ++j) {
            if (s[j]=='1') g[p[i]].emplace_back(p[j]);
        }
    }

    vector dis(n,vector<int>(n,1e9));
    auto bfs=[&](int s, vector<int>& dis) {
        dis[s]=0; queue<int> q; q.emplace(s);
        while (size(q)) {
            int u=q.front(); q.pop();
            for (auto v: g[u]) if (dis[v]>dis[u]+1) q.emplace(v), dis[v]=dis[u]+1;
        }
    };
    array<array<bitset<400>,400>,400> f{};

    for (int i=0; i<n; ++i) {
        bfs(i,dis[i]);
        for (int j=0; j<n; ++j) f[i][dis[i][j]].set(j);
        for (int j=n-2; ~j; --j) f[i][j]|=f[i][j+1];
        // f[i][j]: { t: dis(t,i)>=j }
    }

    auto check=[&](int L) {
        for (int u=0; u<n; ++u)
            for (int v=u+1; v<n; ++v) {
                bool flag=true;
                for (int s=0; s<n; ++s) {
                    // dis[s][t]>=L+1
                    // dis[v][t]>=L+1-dis[s][u]
                    // dis[u][t]>=L+1-dis[s][v]
                    int a=max(0,L+1-dis[s][u]), b=max(0,L+1-dis[s][v]);
                    if ((f[s][L+1]&f[v][a]&f[u][b]).any()) {
                        flag=false; break;
                    }
                }
                if (flag) return true;
            }
        return false;
    };

    int l=0, r=(n+1)/2;
    while (l<r) {
        int mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
}();
}