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

#define pb push_back

const int MAXN = 400 + 17;

vector<int> graf[MAXN];
int odl[MAXN][MAXN];
bool odw[MAXN];
queue<int> d;
string s;
int n;

void BFS (int start) {
    while (!d.empty()) {
        d.pop();
    }
    d.push(start);
    for (int i = 1; i <= n; i ++) {
        odl[start][i] = INT_MAX;
        odw[i] = false;
    }
    odw[start] = true;
    odl[start][start] = 0;
    while (!d.empty()) {
        int v = d.front();
        d.pop();
        for (auto x : graf[v]) {
            if (!odw[x]) {
                odw[x] = true;
                odl[start][x] = odl[start][v] + 1;
                d.push(x);
            }
        }
    }
}

void rozw() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> s;
        for (int j = 0; j < n; j ++) {
            if (s[j] == '1') {
                graf[i].pb(j + 1);
            }
        }
    }

    for (int i = 1; i <= n; i ++) {
        BFS(i);
    }

    int wyn = n;

    for (int i = 1; i <= n; i ++) {
        for (int j = i + 1; j <= n; j ++) {
            int aktwyn = 0;
            for (int x = 1; x <= n; x ++) {
                for (int y = x + 1; y <= n; y ++) {
                    aktwyn = max(aktwyn, min({odl[x][y], odl[x][i] + odl[j][y], odl[x][j] + odl[i][y]}));
                }
            }
            wyn = min(wyn, aktwyn);
        }
    }

    cout << wyn << "\n";

    for (int i = 1; i <= n; i ++) {
        graf[i].clear();
        for (int j = 1; j <= n; j ++) {
            odl[i][j] = 0;
        }
    }
}

int main () {
    ios::sync_with_stdio(); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while (t --) {
        rozw();
    }


    return 0;
}