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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 4e2 + 5;
const int inf = 1e8 + 5;

int tabel[nmax][nmax][nmax];
int dist[nmax][nmax];
int contribA[nmax], contribB[nmax];

void testcase() {
   int n;
   cin >> n;
   for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
         char ch;
         cin >> ch;
         dist[i][j] = (ch == '0'? inf : 1);
      }
      dist[i][i] = 0;
   }
   
   for(int h = 0; h < n; h++) {
      for(int i = 0; i < n; i++) {
         for(int j = 0; j < n; j++)
            dist[i][j] = min(dist[i][h] + dist[h][j], dist[i][j]);
      }
   }
   
   int best = n;
   
   for(int y = 0; y < n; y++) {
      for(int I = 0; I < n; I++) {
         fill(contribA, contribA + n + 2, -inf);
         fill(contribB, contribB + n + 2, -inf);
         for(int i = 0; i < n; i++) {
            const int a = dist[y][i], b = dist[I][i]; // [x^c] = max(min(a + c, b))
            if(b < a) contribB[0] = max(contribB[0], b);
            else {
               const int c = b - a;
               contribA[c] = max(contribA[c], b);
               contribB[c + 1] = max(contribB[c + 1], b);
            }
         }
         
         for(int i = n - 1; i >= 0; i--) contribA[i] = max(contribA[i + 1] - 1, contribA[i]);
         for(int i = 1; i <= n; i++) contribB[i] = max(contribB[i], contribB[i - 1]);
         for(int c = 0; c <= n; c++) tabel[y][I][c] = max(contribA[c], contribB[c]);
      }
   }
   
   
   for(int y = 0; y < n; y++) {
      for(int x = 0; x < n; x++) {
         int worst = -1;
         for(int I = 0; I < n; I++)
            worst = max(worst, min(tabel[y][I][min(n, dist[I][x])], tabel[x][I][min(n, dist[I][y])]));
         best = min(best, worst);
      }
   }
   
   cout << best << '\n';
   return;
}

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int t;
   cin >> t;
   while(t--) testcase();
   
}

/**
      Binecuvanteaza Doamne Ukraina.
--
*/