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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MX=402,ME=MX*MX/2;
int t,n,tot,q[MX][MX],dst[MX][MX],d[MX],e[ME];
pii p[ME],cp[ME];
char s[MX][MX];
bool was[MX];
mt19937 rng(17);
bool cmp(const pii& x, const pii& y) {
  return dst[x.first][x.second]>dst[y.first][y.second];
}
int main() {
  scanf("%d",&t);
  while (t--) {
    scanf("%d",&n);
    for (int i=0; i<n; i++) scanf("%s",s[i]);
    for (int i=tot=0; i<n; i++) {
      for (int k=0; k<n; k++) was[k]=false;
      q[i][0]=i;
      was[i]=true;
      for (int fi=0, fr=1; fi<fr; fi++) {
        int x=q[i][fi];
        for (int j=0; j<n; j++) if (s[x][j]=='1' && !was[j]) {
          was[j]=true;
          q[i][fr++]=j;
          dst[i][j]=dst[i][x]+1;
        }
      }
      for (int j=0; j<i; j++) { p[tot]=cp[tot]=make_pair(i,j); tot++; }
    }
    sort(p,p+tot,cmp);
    shuffle(cp,cp+tot,rng);
    for (int k=0; k<tot; k++) e[k]=dst[p[k].first][p[k].second];
    int best=e[0];
    for (int ii=0; ii<tot; ii++) {
      int i=cp[ii].first;
      int j=cp[ii].second;
      for (int k=0; k<n; k++) d[k]=min(dst[i][k],dst[j][k]);
      int mx=0;
      for (int k=0; k<tot; k++) {
        int cur=min(e[k],d[p[k].first]+d[p[k].second]);
        if (cur>mx) {
          mx=cur;
          if (mx>best) break;
        }
      }
      best=min(best,mx);
    }
    printf("%d\n",best);
  }
  return 0;
}