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
#include <bits/stdc++.h>
using namespace std;
int d[400][400];
int g[400][400];
bool f[400],h[400];
bool r;
char x;
int n,k,t,i,a,j,b;
int z,m,y,S,L,P;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	for (i=0;i<t;i++) {
		cin >> n;
		for(j=0;j<n;j++) {
			for(k=0;k<n;k++) {
				cin >> x;
				if(j==k) continue;
				if(x=='1')
					d[j][k]=1;
				else
					d[j][k]=1000;
			}
			
		}
		for(j=0;j<n;j++) 
			for(k=0;k<n;k++) 
				for(m=0;m<k;m++)
					if(d[j][k]+d[j][m]<d[k][m]) {
						d[k][m]=d[j][k]+d[j][m];
						d[m][k]=d[k][m];
						}
		
		z=0;
		for(j=0;j<n;j++) 
			for(k=0;k<j;k++) 
				if(z<d[j][k]) z=d[j][k];
		L=0;
		P=z+1;
		
		while(L<P) {
			S=(L+P)/2;
			for(j=0;j<n;j++) 
				for(k=0;k<n;k++)
					g[j][k]=0;
			for(j=0;j<n;j++) 
				for(k=0;k<n;k++)
					if(d[j][k]>S) 
						for(b=0;b<n;b++)
							if(g[b][j]<d[b][k])
								g[b][j]=d[b][k];
			r=0;
			
			for(a=0;a<n;a++) {
				for(b=0;b<a;b++) {
					r=1;
					for(j=0;j<n;j++) 
						if(g[b][j]+d[a][j]>S && g[a][j]+d[b][j]>S) {r=0;break;}
					if(r) break;
					}
				if(r)
					break;
				//cout << a << '\n';
				}
				if(r) P=S;
				else L=S+1;	
				//cout << L << ' ' << P <<"\n";
				//return 0;					
				}
			
			cout << L << '\n';
				
			}

		
		

					
				
	}