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
#include<iostream>
#include<algorithm>
using namespace std;
int t,n;
#define REP(i,n) for(int i=0;i<n;++i)
string s;
#define INF 1000000000
int d[512][512],g[512][512];
void lower(int&a,int b){
  if(b<a)a=b;
}
void raise(int&a,int b){
  if(b>a)a=b;
}
int main(){
  cin>>t;
  while(t--){
    cin>>n;
    REP(i,n){
      cin>>s;
      REP(j,n)g[i][j]=(s[j]=='1'?1:(i==j?0:INF));
    }

    REP(i,n)REP(j,n)d[i][j]=g[i][j];
    REP(k,n)REP(i,n)REP(j,n)lower(d[i][j],d[i][k]+d[k][j]);
    int bak=0;
    REP(i,n)REP(j,n)raise(bak,d[i][j]);

    int a,b;
    REP(i,n)REP(j,n)if(bak==d[i][j]){a=i;b=j;}
    d[a][b]=d[b][a]=0;

    REP(k,n)REP(i,n)REP(j,n)lower(d[i][j],d[i][k]+d[k][j]);
    bak=0;
    REP(i,n)REP(j,n)raise(bak,d[i][j]);

    cout<<bak<<endl;

  }
  return 0;
}