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
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
const int MAX_N = 400;//                    ZMIEŃ
int dist[MAX_N][MAX_N];
//int spec[MAX_N][MAX_N];
//bool is_valid[MAX_N][MAX_N];
int n;

/*
//FUNKCJA DO SPRAWDZANIA CZY ISTNIEJE TELEPORT ZMNIEJSZAJĄCY WSZYSTKIE NAJKRÓTRZE ŚCIEŻKI DO DŁUGOŚCI m
bool is_enough(int m) {
	//ITERATE OVER ALL POSSIBLE CONFIGURATIONS (i,j) OF A TELEPORTER
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			spec[i][j] = MAX_N + 1;
			is_valid[i][j] = true;
		}
	}
	for (int x_i = 0; x_i < n; x_i++) {
		for (int x_j = x_i + 1; x_j < n; x_j++) {
			if (dist[x_i][x_j] > m) {
				for (int a = 0; a < n; a++)
					spec[a][x_j] = std::min(spec[a][x_j], m - dist[a][x_i]);
			}
		}
	}
	for (int a = 0; a < n; a++) {
		for (int x_j = 0; x_j < n; x_j++) {
			for (int b = 0; b < n; b++) {
				if (dist[b][x_j] > spec[a][x_j])
					is_valid[a][b] = false;
			}
		}
	}

	for (int a = 0; a < n; a++) {
		for (int b = 0; b < n; b++) {
			if (is_valid[a][b] && is_valid[b][a])
				return true;
		}
	}
	return false;
}
*/
int main()
{
	int t;
	std::cin >> t;
	for (int test = 0; test < t; test++) {
		std::cin >> n;
		char c;
		for (int i=0; i < n; i++) {
			for (int j=0; j < n; j++) {
				std::cin >> c;
				if (c == '0') { 
					if (i != j) dist[i][j] = MAX_N * 10;
					else dist[i][j] = 0;

				}
				else dist[i][j] = 1;
			}
		}


		//OBLICZAM NAJKRÓTSZE ODLEGŁOŚCI POMIEDZY MIASTAMI
		for (int r = 0; r < n; r++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					dist[i][j] = std::min(dist[i][j], dist[i][r] + dist[r][j]);
				}
			}
		}
		
		int max_path = 0;
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				max_path = std::max(dist[x][y], max_path);
			}
		}
		
		int best = MAX_N +10;
		for (int a = 0; a < n; a++) {
			for (int b = a+1; b < n; b++) {
				int max_path = 0;
				for (int x_i = 0; x_i < n; x_i++) {
					for (int x_j = x_i+1; x_j < n; x_j++) {
						int best_teleport = std::min(dist[x_i][a] + dist[x_j][b], dist[x_i][b] + dist[x_j][a]);
						int shortest_dist = std::min(dist[x_i][x_j], best_teleport);
						max_path = std::max(max_path, shortest_dist);
					}
				}
				best = std::min(best, max_path);
			}
		}
		std::cout << best << "\n";
		/*
		//std::cout << "max path " << max_path << "\n";
		//PRZESZUKIWANIEM BINARNYM ZNAJDUJE NAJMNIEJSZE m, ŻE TELEPORT ZMNIEJSZA NAJKRÓTRZE ŚCIEŻKI DO m.
		int a = 0; 
		int b = max_path;
		std::cout << "max_path " << max_path << "\n";
		int mid;
		while (a + 1 < b) {
			mid = (a + b) / 2;
			bool val = is_enough(mid);
			std::cout << "is enough " << mid << (val ? "YES\n" : "NO\n");
			if (val) b = mid;
			else a = mid;
		}
		std::cout << b;
		//std::cout <<"odp: " << b << "\n";
		*/
	}
}