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
 98
 99
100
101
102
103
104
// Author: Olaf Surgut (surgutti)
// Created on 10-03-2025 13:12:55
#include "bits/stdc++.h"
using namespace std;

// #define int long long
#define ll long long
#define ld long double

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x),end(x)
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)

auto& operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")";}
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for (auto e : x) o << ","+!i++ << e;
	return o << "}";}

#ifdef LOCAL
#define debug(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define debug(...)
#endif

#define rep(i,a,b) for(int i = a; i < (b); i++)
using pii = pair<int, int>;
using vi = vector<int>;

const int N = 400 + 7;
const int inf = 1e9;

int n, d[N][N];

mt19937 rng(23234424);

void solve() {
	cin >> n;
	FOR(i, 1, n) {
		string row;
		cin >> row;

		FOR(j, 1, n) {
			if (row[j - 1] == '0')
				d[i][j] = inf;
			else
				d[i][j] = 1;
		
			if (i == j)
				d[i][j] = 0;
		}
	}

	FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n)
		d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

	vector<pii> all_pairs, order;
	FOR(i, 1, n) FOR(j, i + 1, n) {
		all_pairs.eb(i, j);
		order.eb(i, j);
	}
	sort(all(all_pairs), [&](pii a, pii b) {
		return d[a.st][a.nd] > d[b.st][b.nd];
	});

	shuffle(all(order), rng);

	int ans = N;

	for (auto const& [i, j] : order) {
		int now = 0;
		FOR(k, 1, n)	now = max(now, min(d[i][k], d[j][k]));

		for (auto const& [a, b] : all_pairs) {
			if (d[a][b] <= now || ans <= now) {
				break;
			}

			now = max(now, min(d[i][a] + d[j][b], d[i][b] + d[j][a]));
		}

		ans = min(ans, now);
	}

	cout << ans << '\n';
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int tt = 1;
	cin >> tt;
	while (tt--)
		solve();

	return 0;
}