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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// clang-format off
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<"}";}
#ifdef DEBUG
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<"\n";}(X)
#else
#define debug(...) {}
#endif
// clang-format on

int T, N, max_path, score = 0;
vector<int> dist;
vector<tuple<int, int, int>> pairs;  // (distance, a, b)
vector<vector<int>> best;
#define V(a, b) ((a) * N + (b))
const int INF = numeric_limits<int>::max() / 2;

void
warshall()
{
    REP (k, N) {
        REP (a, N) {
            REP (b, N)
                dist[V(a, b)]
                  = min(dist[V(a, b)], dist[V(a, k)] + dist[V(k, b)]);
        }
    }
}

int
with_merged(int a, int b)
{
    int this_score = 0;
    for (const auto& vert_pair : pairs) {
        const auto& [d, u, v] = vert_pair;
        int nd                = min(
          d, min(dist[V(a, u)] + dist[V(b, v)], dist[V(a, v)] + dist[V(b, u)]));
        this_score = max(this_score, nd);
    }
    return this_score;
}

bool
can_improve(int a, int b)
{
    REP (u, N) {
        if (dist[V(a, u)] > dist[V(b, u)]) swap(a, b);  // let a be closer to u
        if (dist[V(a, u)] + best[u][b] >= score) return false;
    }
    return true;
}

void
add_to_best(int u, int v)
{
    auto& bu = best[u];
    REP (b, N) bu[b] = max(bu[b], dist[V(v, b)]);
}

int
solve()
{
    cin >> N;
    dist.resize(N * N);
    REP (a, N) {
        string str;
        cin >> str;
        REP (b, N) dist[V(a, b)] = (str[b] == '0' ? INF : 1);
    }

    // Find all pair distances and sort them by distance
    warshall();
    REP (v, N) dist[V(v, v)] = 0;
    pairs.clear();
    REP (a, N)
        FOR (b, a + 1, N - 1) pairs.emplace_back(dist[V(a, b)], a, b);
    sort(pairs.begin(), pairs.end(), greater<tuple<int, int, int>>());
    score = max_path = get<0>(pairs.front());

    // best[u][b] : greatest d(b, v) st. d(u, v) >= score
    best.assign(N, vector<int>(N));
    auto to_best = pairs.begin();
    while (to_best < pairs.end() && get<0>(*to_best) >= score) {
        add_to_best(get<1>(*to_best), get<2>(*to_best));
        add_to_best(get<2>(*to_best), get<1>(*to_best));
        ++to_best;
    }

    REP (a, N) {
        FOR (b, a + 1, N - 1) {
            if (dist[V(a, b)] <= max_path - score) continue;

            // Check if merge'ing a and b can anyhow improve score
            if (!can_improve(a, b)) continue;

            auto this_score = with_merged(a, b);
            debug(a, b, this_score);
            score = min(score, this_score);

            // Include all pairs >= score
            while (to_best < pairs.end() && get<0>(*to_best) >= score) {
                add_to_best(get<1>(*to_best), get<2>(*to_best));
                add_to_best(get<2>(*to_best), get<1>(*to_best));
                ++to_best;
            }
        }
    }
    return score;
}

int
main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> T;
    while (T--) cout << solve() << "\n";
    return 0;
}