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
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> x; 
int n;

void bfs(int u, vector<vector<int>>& dist, vector<string>& graph){
	dist[u][u] = 0;
	queue<int> q; q.push(u);

	while(!q.empty()){
		int v = q.front(); q.pop();
		for(int i=0; i<n; i++){
			if(dist[u][i] != -1 || graph[v][i] == '0') continue;
			dist[u][i] = dist[u][v] + 1;
			x.push_back({-dist[u][i], rand(), u, i});
			q.push(i);
		}
	}

}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);
	
	int sets; cin>>sets;
	while(sets--){
		x.clear();
		cin>>n;
		vector<string> graph(n);
		for(int i=0; i<n; i++) cin>>graph[i];

		vector<vector<int>> dist(n, vector<int>(n, -1));
		for(int i=0; i<n; i++){
			dist[i][i] = 0;
			bfs(i, dist, graph);
		}

		sort(x.begin(), x.end());

		int best = 0;
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				best = max(best, dist[i][j]);
			}
		}


		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				int maxi = 0;
				for(auto e: x){
					int a = dist[e[2]][i] + dist[j][e[3]];
					int b = dist[e[3]][i] + dist[j][e[2]];
					int shorter = min(-e[0], min(a, b));
					if(maxi >= -e[0]) break;
					maxi = max(maxi, shorter);
				}

				best = min(best, maxi);
			}
		}

		cout<<best<<'\n';
	}
	return 0;
}