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
119
120
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target ("avx2")
//#pragma GCC target ("avx")
//#pragma GCC target ("native")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
typedef long long LL;

int odl[400][400];
//int ans[400][400];
int n;
 
void floyd() {
	for (int j = 0; j < n; j++)
		for (int i = 0; i < n; i++)
			for (int k = 0; k < n; k++)
				if (odl[i][k] > odl[i][j] + odl[j][k])
					odl[i][k] = odl[i][j] + odl[j][k];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt;
	cin>>tt;
	while(tt--) {
		cin>>n;
		for(int i=0; i<n; i++){
			string s;
			cin>>s;
			for(int j=0; j<n; j++){
				if(s[j]=='0'){
					if(i != j){
						odl[i][j]=1001;
					}
					else{
						odl[i][j]=0;
					}
				}else{
					odl[i][j]=1;
				}
			}
		}
		int res = 1001;
		floyd();
		
		
		/*for(int k=1; k<=n; k++){
			for(int l=k+1; l<=n; l++){
				for(int i=1; i<=n; i++){
					for(int j=i+1; j<=n; j++){
						int y = odl[k][l];
						if(y > odl[k][i] + odl[j][l]) y = odl[k][i] + odl[j][l];
						if(y > odl[k][j] + odl[i][l]) y = odl[k][j] + odl[i][l];
						ans[i][j] = max(ans[i][j], y);
					}
				}	
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(ans[i][j]>0){
					res = min(res, ans[i][j]);
				}
			}
		}*/
		
		
		vector<tuple<int, int, int>> v;
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				v.push_back({odl[i][j], i, j});
			}
		}
		sort(v.begin(), v.end());
		reverse(v.begin(), v.end());
		
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				int x = 0;
				for(auto [a, k, l] : v){
					if(a <= x)break;
					int y = a;
					int q1 = odl[k][i] + odl[j][l];
					int q2 = odl[k][j] + odl[i][l];
					if(y > q1) y = q1;
					if(y > q2) y = q2;
					if(y > x) x=y;
				
				}
				if(res > x) res = x;
			}
		}
		
		
		/*for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				int x = 0;
				for(int k=0; k<n; k++){
					for(int l=k+1; l<n; l++){
						int y = odl[k][l];
						int q1 = odl[k][i] + odl[j][l];
						int q2 = odl[k][j] + odl[i][l];
						if(y > q1) y = q1;
						if(y > q2) y = q2;
						if(y > x) x=y;
					}
				}
				if(res > x) res = x;
			}
		}*/
		
		cout<<res<<"\n";
	}
	return 0;
}