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

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxn = 407, inf = 1e9 + 7;
int n;
bool g[maxn][maxn];
bitset<maxn> atDist[maxn][maxn], otherPortal;
int dist[maxn][maxn];

void solve() {
    cin >> n;
    char c;
    rep(i, 0, n) rep(j, 0, n) cin >> c, g[i][j] = c == '1';
    rep(i, 0, n) rep(j, 0, n) atDist[i][j] = 0;
    rep(i, 0, n) {
        queue<int> Q;
        rep(j, 0, n) dist[i][j] = inf;
        dist[i][i] = 0;
        Q.push(i);
        while(!Q.empty()) {
            auto v = Q.front();
            Q.pop();
            DC << " dist[" << i << "][" << v << "] = " << dist[i][v] << eol;
            atDist[i][dist[i][v]][v] = true;
            rep(j, 0, n) if(dist[i][j] == inf && g[v][j]) dist[i][j] = dist[i][v] + 1, Q.push(j);
        }
        rep(j, 1, n) atDist[i][j] |= atDist[i][j - 1];
    }

    int ans = 1e9 + 7;
    otherPortal = 0;
    rep(i, 0, n) {
        // first portal at i, binsearching answer
        int l = 0, r = n, m;
        while(r - l > 1) {
            m = (l + r) / 2;
            rep(j, 0, n) otherPortal[j] = true;
            otherPortal[i] = false;
            rep(j, 0, n) rep(k, 0, n) if(dist[j][k] > m) otherPortal &= atDist[j][m - dist[k][i]] | atDist[k][m - dist[j][i]];
            if(otherPortal.count()) r = m;
            else l = m;
        }
        DC << " with portal at " << i << " we can get answer " << r << eol;
        ans = min(ans, r);
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin >> t;
    rep(i, 0, t) solve();
}