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
#include <iostream>

using namespace std;
using ll = long long;

bool kraw[440][440];
int dist[440][440];

constexpr int inf = 500;

void test() {
	int n;
	cin >> n;
	string s;
	for(int i = 0; i < n; i++) {
		cin >> s;
		for(int j = 0; j < n; j++) {
			kraw[i][j] = (s[j] == '1' ? true : false);
			dist[i][j] = (s[j] == '1' ? 1 : inf);
		}
	}
	for(int k = 0; k < n; k++) {
		for(int x = 0; x < n; x++) {
			for(int y = 0; y < n; y++) {
				dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y]);			
			}
		}
	}
	int ans = n;
	for (int a = 0; a < n; a++) {
		for (int b = a + 1; b < n; b++) {
			int res = 0;
			for(int x = 0; x < n; x++) {
				for(int y = x + 1; y < n; y++) {
					res = max(res, min(dist[x][y], min(dist[a][x], dist[b][x] + min(dist[a][y], dist[b][y]))));
				}
			}
			ans = min(ans, res);
		}
	}
	cout << ans << "\n";
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t-->0) {
		test();
	}
	return 0;
}