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
from collections import deque
import sys

def compute_all_pairs_shortest_paths(n, adjacency_matrix):
    graph = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if adjacency_matrix[i][j] == '1':
                graph[i].append(j)

    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]

    for start in range(n):
        queue = deque([start])    
        dist[start][start] = 0

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if dist[start][neighbor] == INF:
                    dist[start][neighbor] = dist[start][node] + 1
                    queue.append(neighbor)

    return dist

def find_diameter_pairs(dist, n):
    max_dist = -1
    diameter_pairs = []
    
    for u in range(n):
        for v in range(n):
            if u != v:
                if dist[u][v] > max_dist:
                    max_dist = dist[u][v]
                    diameter_pairs = [(u, v)]
                elif dist[u][v] == max_dist:
                    diameter_pairs.append((u, v))
    
    return max_dist, diameter_pairs

def find_central_vertices(dist, n):
    eccentricities = [max(dist[i]) for i in range(n)]
    min_eccentricity = min(eccentricities)
    central_nodes = [i for i in range(n) if eccentricities[i] == min_eccentricity]    
    return central_nodes

def find_best_teleport_placement(n, dist, diameter_pairs, central_vertices):
    best_diameter = float('inf')
    best_teleport = None

    for (a, b) in diameter_pairs[1]:
        new_diameter = compute_new_diameter(dist, n, a, b)
        if new_diameter < best_diameter:
            best_diameter = new_diameter
            best_teleport = (a, b)

    for a in central_vertices:
        for b in range(n):
            if a != b:
                new_diameter = compute_new_diameter(dist, n, a, b)
                if new_diameter < best_diameter:
                    best_diameter = new_diameter
                    best_teleport = (a, b)

    return best_teleport, best_diameter


def compute_new_diameter(dist, n, a, b):
    new_dist = [row[:] for row in dist]

    for u in range(n):
        for v in range(n):
            new_dist[u][v] = min(new_dist[u][v], new_dist[u][a] + new_dist[b][v], new_dist[u][b] + new_dist[a][v])

    return max(max(row) for row in new_dist)

def read_input():
    input_data = sys.stdin.read().strip().split("\n")
    index = 0

    t = int(input_data[index])
    index += 1

    test_cases = []
    
    for _ in range(t):
        n = int(input_data[index])
        index += 1
        adjacency_matrix = []

        for _ in range(n):
            adjacency_matrix.append(input_data[index])
            index += 1

        test_cases.append((n, adjacency_matrix))

    return test_cases

def output_results(results):
    for result in results:
        print(result)

if __name__ == "__main__":
    test_cases = read_input()
    results = []

    for n, adjacency_matrix in test_cases:

        dist = compute_all_pairs_shortest_paths(n, adjacency_matrix)
        diameter_vertices = find_diameter_pairs(dist, n)
        central_vertices = find_central_vertices(dist, n)
        result = find_best_teleport_placement(n, dist, diameter_vertices, central_vertices)    
        results.append(result[1])

    output_results(results)