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
#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define ALL(c) (c).begin(),(c).end()
#define MP make_pair
#define FT first
#define SD second
#define INT(x) int x; scanf("%d", &x)

typedef pair<int,int> PII;

const int INF = 1000000000;
char a[400][401];
int d[400][400];

void test() {
	INT(n);
	REP(i,n) scanf("%s", a[i]);
	REP(i,n) REP(j,n) d[i][j] = a[i][j] == '1' ? 1 : INF;
	REP(i,n) d[i][i] = 0;
	REP(k,n) REP(i,n) REP(j,n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	vector<pair<int, PII> > e;
	REP(i,n) FOR(j,i+1,n) e.PB(MP(-d[i][j], MP(i, j)));
	sort(ALL(e));
	int r = 0;
	REP(i,n) FOR(j,i+1,n) r = max(r, d[i][j]);
	REP(t1,n) FOR(t2,t1+1,n) {
		int d1 = 0;
		FORE(it,e) {
			int d0 = -it->FT, v = it->SD.FT, w = it->SD.SD;
			if (d0 <= d1) break;
			int dd = min(d0, min(d[v][t1] + d[t2][w], d[v][t2] + d[t1][w]));
			d1 = max(d1, dd);
			if (d1 >= r) break;
		}
		r = min(r, d1);
	}
	printf("%d\n", r);
}

int main() {
	INT(t);
	REP(tt,t) test();
}