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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int N = 400;
using B = std::bitset<N>;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector dis(n, std::vector<int>(n, n));
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '1') {
                dis[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        dis[i][i] = 0;
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    
    std::vector vec(n, std::vector<B>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            vec[i][dis[i][j]].set(j);
        }
        for (int j = 1; j < n; j++) {
            vec[i][j] |= vec[i][j - 1];
        }
    }
    
    int ans = n;
    
    auto check = [&](int s, int d) {
        B b {};
        for (int i = 0; i < n; i++) {
            b.set(i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (dis[i][j] > d) {
                    B c {};
                    if (dis[i][s] <= d) {
                        c |= vec[j][d - dis[i][s]];
                    }
                    if (dis[j][s] <= d) {
                        c |= vec[i][d - dis[j][s]];
                    }
                    b &= c;
                }
            }
        }
        return b.any();
    };
    
    for (int i = 0; i < n; i++) {
        while (ans && check(i, ans - 1)) {
            ans--;
        }
    }
    
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}