#1372 그래프의 지름

55  2 s   128 MB  

Description

그래프의 지름이란, 그 그래프에서 임의의 두 점 사이의 최단 거리 중 최대를 말한다.

주어진 그래프에서 지름을 구하는 프로그램을 작성하여라.

 

Input

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 행에는 그래프의 정점의 개수 $N (1 \leq N \leq 100)$ 이 주어진다.

이후 $N$ 행에 걸쳐서 각 행마다 $N$ 개씩의 정수가 주어진다. $i$행 $j$열에 위치한 정수는 $i$번 정점에서 $j$번 정점으로의 간선의 가중치이다.
만약 이 값이 -1이라면 해당하는 간선이 없다는 뜻이다. 각 가중치는 $10^9$ 이하이며, 그래프의 간선에 방향성이 없으므로 $i$행 $j$열에 위치한 값과 $j$행 $i$열에 위치한 값은 같다.

주어진 그래프는 항상 연결 그래프이다.

 

Output

각 테스트 케이스에 대해 한 행에 하나씩 그래프의 지름을 출력한다.

 

Sample Input

Sample Output

1
4
-1 5 -1 -1
5 -1 5 -1
-1 5 -1 5
-1 -1 5 -1
15