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
import numpy as np
def multiply(matrix1,matrix2):
    return np.matmul(matrix1,matrix2)

def diag(n):
    return np.diag(np.ones(n))

def find_optimal_place_for_teleport(matrix, n):
    sum_ = matrix + diag(n)
    i = 1
    indexes = False
    powered = matrix
    while True:
        if sum_.all():
            # są same 0
            return i, indexes
        indexes = np.where(sum_==0)
        if len(indexes[0])==2:
            # zostały tylko dwa miejsca z 0 (czyli nie ma drogi tylko między dwoma miastami)
            return i, (indexes[0][0],indexes[1][0])
        else:
            # robimy iterację
            i+=1
            i_th_power = multiply(matrix,powered)
            powered = i_th_power
            sum_ = sum_ + powered


def find_no(matrix, n):
    sum_ = matrix + diag(n)
    i = 1
    powered = matrix
    while True:
        if sum_.all():
            # są same 0
            return i
        else:
            # robimy iterację
            i+=1
            i_th_power = multiply(matrix, powered)
            powered = i_th_power
            sum_ = sum_ + powered

def main(matrix, n):
    no, index = find_optimal_place_for_teleport(matrix,n)

    if index:
        matrix[index[1]][index[0]]=1
        matrix[index[0]][index[1]]=1
        no = find_no(matrix, n)
    print(no)


if __name__ == "__main__":
    import sys
    t = int(sys.stdin.readline().strip("\n"))
    #print(t)
    #print("###########")
    for i in range(t):
        n = int(sys.stdin.readline().strip("\n"))
        #print(f"{n=}")
        rows = []
        for row in range(n):
            rows.append([
                int(el) 
                for el in list(sys.stdin.readline().strip("\n"))
            ])
        #print(rows)
        matrix = np.array(rows)
        main(matrix,n)