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

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define vec vector
#define pb push_back
#define f first
#define s second

#define stack stack69

using namespace std;

const int N = 448;
int n;

bitset<N> edges[N];

int dist[N][N];

void get_dist(){
	foru(i, n) foru(j, n){
		if(edges[i][j]) dist[i][j] = 1;
		else dist[i][j] = INT_MAX/3;
	}
	foru(i, n) dist[i][i] = 0;

	foru(k, n) {
		foru(i, n) foru(j, n) {
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
}

vec<pair<int, int>> stack[N];

void get_stack(){
	foru(i, n) {
		stack[i].resize(n);
		foru(j, n) stack[i][j] = {dist[i][j], j};
		sort(stack[i].begin(), stack[i].end());
	}
}

int steps_needed[N][N][N]; //[start][teleport][steps to teleport]

void get_steps(){ // O(n^4/64)
	foru(i, n) foru(j, n) {
		int worst_case_a = 0;
		int stack_index = n-1;

		foru(steps_to_teleport, n){
			while(true){
				if(stack_index < 0) break;
				
				auto p = stack[j][stack_index];
				int case_a = dist[i][p.s];
				int case_b = p.f + steps_to_teleport;
				if (case_a >= case_b) break;
				stack_index --;
				worst_case_a = max(worst_case_a, case_a);
			}

			int worst_case_b = 0;
			if(stack_index>0) worst_case_b = stack[j][stack_index].f + steps_to_teleport;

			steps_needed[i][j][steps_to_teleport] = max(worst_case_a, worst_case_b);
		}
		
	}
}


void solve(){
	cin >> n;
	
	foru(i, n) foru(j, n) {
		char c = ' ';
		while (c != '0' && c != '1') cin >> c;
		edges[i][j] = (c == '1');
	}

	get_dist();
	get_stack();
	get_steps();

	int ans = INT_MAX;

	foru(i, n) fors(j, n, i+1) {
		int subans = 0;
		foru(k, n) {
			int steps = min(
				steps_needed[k][i][dist[k][j]],
				steps_needed[k][j][dist[k][i]]
			);
			subans = max(subans, steps);
		}
		ans = min(ans, subans);
	}

	cout << ans << endl;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    int t; cin >> t;
    foru(_i, t) solve();
    
    return 0;
}