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

vector <int> graf[403];
vector <int> ngraf[403];
bool odw[403][403]{false};

int maks, maks2;

queue <int> K;

void f(int v, int s, int o){
	if(o > maks){
		maks = o;
	}
	for(int i = graf[v].size() - 1; i >= 0; i--){
		if(!odw[s][graf[v][i]]){ 
			K.push(graf[v][i]);
			K.push(s); 
			K.push(o + 1);
			odw[s][graf[v][i]] = true;
		}
	}
}

void BFS(int m){
	for(int i = 1; i <= m; i++){
		K.push(i);
		K.push(i);
		K.push(0);
		odw[i][i] = true;
	}
	maks = -1;
	while(!K.empty()){
		int v = K.front();
		K.pop();
		int s = K.front();
		K.pop();
		int o = K.front();
		K.pop();
		f(v, s, o);
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	int a, b;
	string t;
	cin >> a;
	for(int i = 0; i < a; i++){
		cin >> b;
		maks2 = 999999;
		for(int j = 1; j <= b; j++){
			cin >> t;
			for(int k = 1; k <= b; k++){
				if(t[k - 1] == '0'){
					ngraf[j].push_back(k);
				}
				else{ 
					graf[j].push_back(k);
				}
			}
		}
		for(int i = 1; i <= b; i++){
			for(int j = 0; j < ngraf[i].size(); j++){
				if(ngraf[i][j] >= i) continue;
				graf[i].push_back(ngraf[i][j]);
				graf[ngraf[i][j]].push_back(i);
				maks = -1;
				BFS(b);
				maks2 = min(maks, maks2);
				for(int j = 1; j <= b; j++){
					for(int k = 1; k <= b; k++) odw[j][k] = false;
				}
				graf[i].pop_back();
				graf[ngraf[i][j]].pop_back();
			}
		}
		BFS(b);
		maks2 = min(maks, maks2);
		cout << maks2 << '\n';
		for(int i = 1; i <= b; i++){
			for(int j = 1; j <= b; j++) odw[i][j] = false;
			while(graf[i].size() > 0) graf[i].pop_back();
			while(ngraf[i].size() > 0) ngraf[i].pop_back();
		}
	}
	return 0;
}