#include <bits/stdc++.h>
using namespace std;

const int NAX = 400;
const int INF = 1e9+5;

void test_case() {
	int n;
	cin >> n;
	vector<vector<int>> dist(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			dist[i][j] = (s[j] == '1' ? 1 : INF);
		}
		dist[i][i] = 0;
	}
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n; i++) {
			for (int k = 0; k < n; k++) {
				dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k]);
			}
		}
	}
	// far[i][d] -- bitset of nodes at distance >= d from node i
	vector<vector<bitset<NAX>>> far(n, vector<bitset<NAX>>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			far[i][dist[i][j]][j] = 1;
		}
		for (int d = (int) far[i].size() - 1; d >= 1; d--) {
			far[i][d-1] |= far[i][d];
		}
	}
	int answer = n - 1;
	for (int A = 0; A < n; A++) {
		for (int B = A + 1; B < n; B++) {
			auto improve = [&]() {
				for (int i = 0; i < n; i++) {
					int closer = (dist[A][i] < dist[B][i] ? A : B);
					int other = A + B - closer;
					if (dist[closer][i] > answer) {
						return false;
					}
					if ((far[i][answer] & far[other][answer-dist[closer][i]]) != 0) {
						return false;
					}
				}
				return true;
			};
			while (answer > 0 && improve()) {
				answer--;
			}
		}
	}
	cout << answer << "\n";
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		test_case();
	}
}