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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

void solve(){
	using bs = bitset<400>;
	int N;
	cin >> N;
	vector<bs> adj(N);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			char c;
			cin >> c;
			if(c == '1') adj[i][j] = 1;
		}
	}
	vector<vector<int> > dist(N);
	for(int st = 0; st < N; st++){
		vector<int> d_st(N, -1);
		bs vis;
		queue<int> q;
		d_st[st] = 0;
		q.push(st);
		vis[st] = 1;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			bs g = adj[v] & (~vis);
			for(int w = g._Find_first(); w < N; w = g._Find_next(w)){
				d_st[w] = d_st[v] + 1;
				q.push(w);
				vis[w] = 1;
			}
		}
		dist[st] = d_st;
	}
	// fix D?
	// store: grid of d(x, a), d(y, b), d(x, y).
	// need d(x,y) > D, d(x,a) + d(y,b) > D

	int st = -1;
	int en = N;
	while(st + 1 < en){
		int mid = st + (en-st) / 2;
		int D = mid;
		// s -> a -> b -> t
		vector<vector<int> > cands(N);
		{
			vector<bs> more_than_D(N);
			for(int a = 0; a < N; a++){
				for(int b = 0; b < N; b++){
					if(dist[a][b] > D){
						more_than_D[a][b] = 1;
					}
				}
			}
			for(int s = 0; s < N; s++){
				vector<bs> dist_allowed_b(N);
				for(int a = 0; a < N; a++){
					dist_allowed_b[dist[s][a]] |= more_than_D[a];
				}
				// for each b, what is the max dist(a,s) that exists or -1 if not
				vector<int> max_dist(N, -1);
				bs cur;
				for(int d = N-1; d >= 0; d--){
					bs new_b = (dist_allowed_b[d] & ~cur);
					for(auto i = new_b._Find_first(); i < N; i = new_b._Find_next(i)){
						max_dist[i] = d;
					}
					cur |= dist_allowed_b[d];
				}
				cands[s] = max_dist;
			}
		}
		bool works = false;
		bs all_bits;
		for(int i = 0; i < N; i++) all_bits[i] = 1;
		vector<bs> cand_which_t(N, all_bits);
		for(int b = 0; b < N; b++){
			vector<bs> dist_at_most(N);
			for(int a = 0; a < N; a++){
				dist_at_most[dist[b][a]][a] = 1;
			}
			for(int d = 1; d < N; d++){
				dist_at_most[d] |= dist_at_most[d-1];
			}
			for(int s = 0; s < N; s++){
				vector<int>& max_dist = cands[s];
				if(max_dist[b] == -1) continue;
				// dist[b][t] <= D - max_dist[b] if dist[b][t] <= dist[b][s]
				if(dist[b][s] <= D - max_dist[b]){
					// then no constraint
				} else {
					bs bad = dist_at_most[dist[b][s]];
					if(max_dist[b] <= D){
						bad ^= dist_at_most[D - max_dist[b]];
					}
					cand_which_t[s] &= ~bad;
				}
			}
		}
		for(int s = 0; s < N; s++){
			for(int t = 0; t < N; t++){
 				if(cand_which_t[s][t] && cand_which_t[t][s]){
					works = true;
				}
			}
		}
		(works ? en : st) = mid;
	}
	cout << en << '\n';
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
}