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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <algorithm>
#include <deque>
#include <iostream>
#include <queue>
#include <vector>
using ll = long long;

constexpr int MAXN = 400;
constexpr int INFTY = MAXN * MAXN; // is enough

int n;
std::vector<std::vector<int>> graph;
std::vector<std::vector<int>> basedist;

void solve() {
	std::cin >> n;
	
	graph.assign(n, {});
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			char ch;
			std::cin >> ch;
			if (ch == '1') {
				// NB: the other direction is added as well.
				graph[i].push_back(j);
			}
		}
	}
	
	basedist.assign(n, std::vector<int>(n, INFTY));
	
	for (int src = 0; src < n; ++src) {
		std::queue<int> que;
		que.push(src);
		basedist[src][src] = 0;
		
		while (!que.empty()) {
			int x = que.front();
			que.pop();
			
			for (int y : graph[x]) {
				if (basedist[src][y] == INFTY) {
					basedist[src][y] = basedist[src][x] + 1;
					que.push(y);
				}
			}
		}
	}
	
//	for (int i = 0; i < n; ++i) {
//		std::cout << "basedist["<<i+1<<"]:";
//		for (int j = 0; j < n; ++j) {
//			std::cout << ' ' << basedist[i][j];
//		}
//		std::cout << '\n';
//	}
	
	int answer = INFTY;
	
	for (int A = 0; A < n; ++A) {
		for (int B = A + 1; B < n; ++B) {
//			std::cout << "A, B = " << A+1 << ", " << B+1 << "\n";
			int maxdist = 0;
			for (int x = 0; x < n; ++x) {
				for (int y = x + 1; y < n; ++y) {
					int xydist = std::min({
						basedist[x][y],
						basedist[x][A] + basedist[B][y],
						basedist[x][B] + basedist[A][y],
					});
//					if (A+1==1&&B+1==7) {
//						std::cout << "x=" << x+1 << ", y=" << y+1 << " => D(x -> y) = " << basedist[x][y] << ", D(x -> AB -> y) = " << (basedist[x][A] + basedist[B][y]) << ", D(x -> BA -> y) = " << (basedist[x][B] + basedist[A][y]) << " => minxydist = " << xydist << '\n';
//					}
					maxdist = std::max(maxdist, xydist);
					if (maxdist >= answer) {
						goto nope;
					}
				}
			}
//			std::cout << " => maxdist=" << maxdist << '\n';
			answer = std::min(answer, maxdist);
			nope:;
		}
	}
	
	std::cout << answer << '\n';
}

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);
	int Z;
	std::cin >> Z;
	while (Z--) {
		solve();
	}
}