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
#include <cstdio>
#include <cassert>
#include <vector>
#include <bitset>
#define FOR(i,p,k) for(int i=(p); i<=(k); ++i)
#define REP(i,k) FOR(i,0,(k)-1)
#define RFOR(i,p,n) for(int i=(p); i>=(n); --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ssize(x) int((x).size())
#define fi first
#define se second
#define V vector
#define pb push_back
#define eb emplace_back
#define C const
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;
typedef C int ci;
typedef C ll cll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
void chmin(auto &a, auto b){a=min(a,b);}
void chmax(auto &a, auto b){a=max(a,b);}
ci inf=1e9;
cll infll=4.5e18;
int I(){
    int z;
    scanf("%d", &z);
    //cin>>z;
    return z;
}
ci ncap=400;
typedef bitset <ncap> bst; // https://media.tenor.com/Q4bqK52EH-0AAAAe/surprised-black.png
bst rbst;
void ans(){
    ci n=I();
    V <vi> pol(n, vi(n));
    REP(p, n){
        scanf("\n");
        REP(k, n)
            pol[p][k]=getchar_unlocked() == '1' ? 1 : inf;
        pol[p][p]=0;
    }
    REP(k, n)
        REP(i, n)
            REP(j, n)
                chmin(pol[i][j], pol[i][k]+pol[k][j]);
    V <V <bst>> wym(n, V <bst>(n, bst())); // [l][a]
    REP(l, n)
        REP(a, n)
            REP(b, n)
                if (pol[a][b]>l)
                    wym[l][a].set(b);
    int w=n-1;
    REP(c, n)
        FOR(d, c+1, n-1){
            V <bst> zleb_t(w, rbst);
            {
                REP(b, n){
                    ci o=min(pol[c][b], pol[d][b]);
                    if (o<w)
                        zleb_t[o].reset(b);
                    else
                        goto done;
                }
                REP(x, w-1)
                    zleb_t[x+1]&=zleb_t[x]; // O(n^4/64).
            }
            while (w>0){
                ci l=w-1;
                REP(a, n){
                    ci x=min(pol[c][a], pol[d][a]);
                    if (x>l||(zleb_t[l-x]&wym[l][a]).any()) // O((n^2+n)*n*n/64)
                        goto done;
                }
                --w;
            }
            done:;
        }
    printf("%d\n", w);
    return;
}
int main(){
    rbst.flip();
    //ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    tt=I();
    while (tt--)ans();
}