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
def find_max_road(graph):
    max = -1
    max_node = None

    for node in graph:
        cost = len(graph[node])
        if cost > max:
            max = cost
            max_node = node

    return max_node

def start(): # work
    t = int(input())
    for _ in range(t): # work
        graph = {}
        n = int(input())
        i = 0
        for _ in range(n): # work
            d = list(input())
            j = 0
            while j < n: # work
                if i != j:
                    if str(int(i + 1)) not in graph: # work
                        graph[str(int(i + 1))] = {}
                    if int(d[j]) == 1: # work
                        graph[str(int(i + 1))][str(int(j + 1))] = 1

                j += 1
            i += 1

        c = find_max_road(graph)
        print(c)

start()