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
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

const int INF = 1e6 + 7;

#define LOCAL false

const int MAXV = 407;
int V;
string mat[MAXV];
int dst[MAXV][MAXV];

bitset<401> nei[MAXV][MAXV]; // nei[v][dep]

int perm[MAXV];
int perm2[MAXV];

int cnt = 0;
bool ok(int d) {
    rep1(j, V) rep1(i, j-1) {
        int s1 = perm[i];
        int s2 = perm[j];
        bool flag = true;
        int xd = 0;
        rep1(ii, V) {
            cnt++;
            xd = ii;
            int v1 = perm2[ii];
            int d2 = d-min(dst[v1][s1], dst[v1][s2]);
            if (d2<0) {
                flag = false;
                break;
            }
            bitset<401> reach = nei[v1][d]|nei[s1][d2]|nei[s2][d2];
            if (reach.count() != V) {
                flag = false;
                break;
            }
        }
        if (flag) return true;
    }
    return false;
}

mt19937 rng;
void solve() {
    cin >> V;
    rep(i, V) cin >> mat[i];

    rep1(v1, V) rep1(v2, V) {
        if (mat[v1-1][v2-1] == '1') dst[v1][v2] = 1;
        else dst[v1][v2] = INF;
    }
    rep1(v, V) dst[v][v] = 0;
    rep1(x, V) rep1(v1, V) rep1(v2, V) dst[v1][v2] = min(dst[v1][v2], dst[v1][x]+dst[v2][x]);

    rep1(v1, V) rep1(v2, V) nei[v1][dst[v1][v2]][v2] = true;
    rep1(v, V) rep1(d, V) nei[v][d] |= nei[v][d-1];

    iota(perm+1, perm+1+V, 1);
    shuffle(perm+1, perm+1+V, rng);
    iota(perm2+1, perm2+1+V, 1);
    shuffle(perm2+1, perm2+1+V, rng);

    int l = 1;
    int r = V;
    while (l<r) {
        int mid = (l+r)/2;
        if (ok(mid)) r = mid;
        else l = mid+1;
        cnt = 0;
    }
    cout << l << "\n";

    rep1(v, V) rep(d, V+1) nei[v][d].reset();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (LOCAL) {
        ignore=freopen("io/in", "r", stdin);
        ignore=freopen("io/out", "w", stdout);
    }

    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}