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
def floyd_warshall(n, graph):
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] == '1':
                dist[i][j] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

def znajdz_minimalny_bak(n, graph):
    dist = floyd_warshall(n, graph)
    max_dist = max(max(row) for row in dist)
    best_fuel = max_dist

    for a in range(n):
        for b in range(a + 1, n):
            new_dist = [row[:] for row in dist]
            for i in range(n):
                for j in range(n):
                    new_dist[i][j] = min(new_dist[i][j], new_dist[i][a] + new_dist[b][j])
                    new_dist[i][j] = min(new_dist[i][j], new_dist[i][b] + new_dist[a][j])
            best_fuel = min(best_fuel, max(max(row) for row in new_dist))

    return best_fuel

def main():
    t = int(input())
    results = []

    for _ in range(t):
        n = int(input())
        graph = [input().strip() for _ in range(n)]
        results.append(str(znajdz_minimalny_bak(n, graph)))

    print("\n".join(results))

if __name__ == "__main__":
    main()