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
# include <bits/stdc++.h>
typedef int ll;
using namespace std;
# define For(i , l , r) for(int i = (l); i <= (r); i++)
# define Rep(i , n) For(i , 0 , (n) - 1)
# define size(x) (ll)x.size()
# define all(x) x.begin(),x.end()
# define MAXN 8002
const ll inf = 1e9 + 7;
const ll mod = 998244353;
ll n , m , k , ans = 0 , qq , t , timer = 0;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> qq;
    while (qq--) {
        cin >> n;
        vector g(n + 5 , vector(n + 5 , '0'));
        vector dist(n + 5 , vector(n + 5 , inf));
        For (i , 1 , n) {
            For (j , 1 , n) {
                cin >> g[i][j];
                if (i == j) dist[i][j] = 0;
                if (g[i][j] == '1') dist[i][j] = 1;
            }
        }
        For (i , 1 , n) {
            For (j , 1 , n) {
                if (i == j) continue;
                For (k , 1 , n) {
                    if (i == k || j == k) continue;
                    dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
                }
            }
        }
      //  cout << 1 << endl;
        vector<ll>ind(n);
        Rep (i , n) ind[i] = i + 1;
        random_shuffle(all(ind));
        auto ind2 = ind;
        random_shuffle(all(ind2));
        ans = inf;
        For (i , 1 , n) {
            For (j , i + 1 , n) {
                ll v1 = ind[i - 1] , v2 = ind[j - 1] , res = -inf;
                if (v1 == v2) continue;
                For (x , 1 , n) {
                    For (y , x + 1 , n) {
                        ll vx = ind2[x - 1] , vy = ind2[y - 1];
                        if (vx == vy) continue;
                        res = max(res , min({dist[vx][vy] , dist[vx][v1] + dist[v2][vy] , 
                            dist[vx][v2] + dist[v1][vy]}));
                        if (res >= ans) break;
                      //  cout << ++timer << endl;
                    }
                    if (res >= ans) break;
                }
                ans = min(ans , res);
            }
        }
        cout << ans << "\n";
    }
}
/*

*/