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
import sys

def floyd_warshall(n, dist):
    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_min_bak(n, macierz):
    INF = 10**9
    
    # Tworzenie macierzy odległości
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif macierz[i][j] == '1':
                dist[i][j] = 1
    
    # Obliczenie wszystkich najkrótszych ścieżek
    dist = floyd_warshall(n, dist)
    
    # Znalezienie najgorszego przypadku przed dodaniem teleportu
    srednica_przed = max(max(wiersz) for wiersz in dist)
    
    # Próba dodania teleportu i minimalizacja średnicy
    min_bak = srednica_przed
    for i in range(n):
        for j in range(i + 1, n):
            nowa_dist = [wiersz[:] for wiersz in dist]
            for a in range(n):
                for b in range(n):
                    nowa_dist[a][b] = min(nowa_dist[a][b], nowa_dist[a][i] + nowa_dist[j][b] + 1,
                                                         nowa_dist[a][j] + nowa_dist[i][b] + 1)
            srednica_po = max(max(wiersz) for wiersz in nowa_dist)
            min_bak = min(min_bak, srednica_po)
    
    return min_bak

def main():
    t = int(sys.stdin.readline())
    wyniki = []
    for _ in range(t):
        n = int(sys.stdin.readline())
        macierz = [sys.stdin.readline().strip() for _ in range(n)]
        wyniki.append(str(znajdz_min_bak(n, macierz)))
    
    print("\n".join(wyniki))

if __name__ == "__main__":
    main()