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
125
126
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define mp make_pair
//~ #define r(x) resize(x)
//~ #define rf(x, c) resize(x, c)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
void get_dist(int &n, V<V<int>> &t, V<int> &dist, V<int> &q, int &source){
    dist = V<int>(n, 0);
    int front = 0, back = 0;
    dist[source] = 1, q[back++] = source;
    while(front < back){
        int x = q[front++];
        for(int u : t[x])
            if(!dist[u])
                dist[u] = dist[x]+1, q[back++] = u;
    }
    for(int i = 0; i < n; ++i) --dist[i];
}
void answer(){
    int n; scanf("%d", &n);
    V<V<int>> t(n);
    for(int i = 0; i < n; ++i){
        char c; scanf("\n"); 
        for(int j = 0; j < n; ++j){
            scanf("%c", &c);
            if(c-'0')
                t[i].emplace_back(j);
        }
    }
    V<int> qq(n);
    V<V<int>> dist(n);
    for(int i = 0; i < n; ++i)
        get_dist(n, t, dist[i], qq, i);

    int L = 1, R = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            R = max(R, dist[i][j]);

    const int N = 400;
    bitset<N> emp, full; full.set();
    V<V<int>> d(n, V<int>(n+1, -1)), nxt(n, V<int>(n+1,-1));
    for(int a = 0; a < n; ++a){
        for(int i = 0; i < n; ++i){
            nxt[a][i] = d[a][dist[a][i]];
            d[a][dist[a][i]] = i;
        }
    }

    bitset<N> _a, _b;
    V dist_bitset(n, V(n, bitset<N>())); 
    for(int a = 0; a < n; ++a){
        _a = full;
        for(int i = 0; i < n; ++i){
            int u = d[a][i];
            while(u != -1)
                _a[u] = 0, u = nxt[a][u];
            dist_bitset[a][i] = _a;
        }
    }

    srand(time(0));
    V<int> p(n);
    iota(all(p), 0);
    for(int i = 0; i < N; ++i)
        random_shuffle(all(p));

    while(L < R){
        int k = (L+R)/2;
        V<bitset<N>> m(n), and1(n);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(dist[i][j] > k) m[i].set(j, 1);
        
        bool is_good = 0;
        int a, b;
        for(int A = 0; A < n; ++A){
            for(int B = A+1; B < n; ++B){
                a = p[A], b = p[B];
                bool bad = 0;
                for(int i = 0; i < n; ++i){
                    if((m[i] & 
                        (dist[a][i] <= k ? dist_bitset[b][k-dist[a][i]] : full) &
                        (dist[b][i] <= k ? dist_bitset[a][k-dist[b][i]] : full))
                        != emp){
                            bad = 1;
                            break;
                        }
                }
                if(!bad){ is_good = 1; break; }
            }
            if(is_good) break;
        }
        if(is_good) R = k;
        else L = k+1;
    }

    printf("%d\n", L);
}
int main(){
		int T = 1;
		scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
		for(++T; --T; ) answer();
		return 0;
}