Description

设计一个简易交通查询系统，
能让东大学生查询南京任一高校内从一个地点到另一个地点之间的最短路径。
每次给出一个高校的地图，请计算图中任意两个地点之间的最短路径长度。

Input

地点编号均为int型整数。
先输入int型整数T，表示T组地图的数据：
接下来T组输入：
第一行是该地图的地点数n ( 0 < n < 200 )（注：地图有n个地点，编号从1开始。 ）
第二行是n行n列个数，第i行第j列的数据表示从i号地点到j号地点的距离（-1表示不连通）（无负权回路）

Output

关于每个地图输出任意两个地点之间的最短路径长度，
用一个n×n矩阵表示，第i行第i列的数据表示从i号地点到j号地点的最短路径长度。（用输出-1表示不连通，无最短路径长度）

Sample Input

1
6
0 1 -1 4 4 -1
-1 0 -1 2 -1 -1
-1 -1 0 -1 -1 1
-1 -1 2 0 3 -1
-1 -1 -1 -1 0 3
-1 -1 -1 -1 -1 0

Sample Output

0 1 5 3 4 6
-1 0 4 2 5 5
-1 -1 0 -1 -1 1
-1 -1 2 0 3 3
-1 -1 -1 -1 0 3
-1 -1 -1 -1 -1 0