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

def read_matrix(n):
    matrix = []
    for _ in range(n):
        data = input().strip()
        row = [int(char) for char in data]
        matrix.append(row)
    return matrix

def bfs_shortest_paths(graph, start):
    n = len(graph)
    distances = [-1] * n
    queue = deque([start])
    distances[start] = 0
    
    while queue:
        u = queue.popleft()
        for v in range(n):
            if graph[u][v] == 1 and distances[v] == -1:
                distances[v] = distances[u] + 1
                queue.append(v)
            elif graph[u][v] == 0.1 and distances[v] == -1:
                distances[v] = distances[u]
                queue.append(v)

    return distances

def graph_diameter_and_farthest_nodes(incidence_matrix):
    n = len(incidence_matrix)
    diameter = 0
    farthest_pair = None 
    
    for u in range(n):
        distances = bfs_shortest_paths(incidence_matrix, u)
        max_distance = max(distances)
        if max_distance > diameter:
            diameter = max_distance
            for v, d in enumerate(distances):
                if d == max_distance:
                    farthest_pair = (u, v)
                    break 
    
    return diameter, farthest_pair


def main():
    t = int(input())
    
    for _ in range(t):
        n = int(input())

        matrix = read_matrix(n)
        diameter, farthest_nodes = graph_diameter_and_farthest_nodes(matrix)

        matrix[farthest_nodes[0]][farthest_nodes[1]] = 0.1
        matrix[farthest_nodes[1]][farthest_nodes[0]] = 0.1

        diameter, farthest_nodes = graph_diameter_and_farthest_nodes(matrix)

        print(diameter)

if __name__ == "__main__":
    main()