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
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;
//#define int long long
#define endl '\n'
const int N = 400;
#define us uint8_t
#define us2 uint16_t
us A[N][N];
us B[N];
inline us add(us a, us b){
	//if(a+(us2)b > 255)return 255;
	//return a+b;//max(a+b, a|b);
	
	return (((((a+(us2)b)&256) >> 7))*255)|(a+(us2)b);
}

main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int z;
	cin >> z;
	while(z--){
		int n;
		cin >> n;
		vector <string> a(n);
		for(int i = 0; i < n; ++i)cin >> a[i];
		//vector <vector <us> > A(n, vector <us> (n));
		int n2 = n;
		while(n2 % 16 != 0)++n2;
		for(int i = 0; i < n2; ++i){
			for(int j = 0; j < n2; ++j){
				A[i][j] = 0;
			}
		}

		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				if(a[i][j] == '1')A[i][j] = 1;
				else A[i][j] = (uint8_t)255;
			}
			A[i][i] = 0;
		}

		us diam = 0, x = 0, y = 0;
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				for(int j = 0; j < n; ++j){
					us w1 = A[i][j];
					us w2 = add(A[i][k], A[k][j]);
					A[i][j] = min(w1, w2);
					diam = max(diam, A[i][j]);
				}
			}
		}

		x = diam;
		for(int c = 0; c < n; ++c){
			for(int d = c+1; d < n; ++d){
				y = 0;
				for(int i = 0; i < n2; ++i){
					//us u1 = A[i][c];
					//us u2 = A[i][d];
					us u1 = min(A[i][c], A[i][d]);
					for(int j = 0; j < n2; ++j){
						us w1 = A[i][j];
						/*us w2 = add(u1, A[d][j]);
						us w3 = add(u1, A[c][j]);
						us w4 = min(w2, w3);*/
						us w4 = add(u1, min(A[c][j], A[d][j]));
						
						us w = min(w1, w4);
						y = max(y, w);
					}
				}
				x = min(y, x);
			}
		}
		cout << (int)x << '\n';
	}
}