Description

幸福的暑假开始啦，小L想出去看看外面的世界。他兴高采烈地走到学校大门，一看手表现在是9:50。他突然想起来，今天似乎有暑期课程，而暑期课程正好在9:50上课！
小L不是神，他不知道从校门到教室需要多少时间，面对一个岔路口，他只会随机选一个岔路口走。
这可怎么办，小L掏出手机想给老师请几分钟的假，请假的时长在保证他一定从学校到教室的情况下，请假的时间最短。
现在需要你帮帮小L，算出他需要请假的时间。

Input

第一行一个int型整数T，代表一共有T组数据。
每组数据的第二行是一个整数n（n<=1000),表示地图有n个顶点。（节点从1开始标号）
接下来n行n列个数，第i行第j个数表示走i号节点到j号节点的这一条路径所需花的分钟数（如果该数为-1，表示此路不通）
校门位于1号点，教室位于n号点，地图中不会有环出现，且所有道路（u，v）可以走仅当序号u<v

Output

输出T行, 每行包括一个整数, 代表每组数据小L需要请假的时长

Sample Input

1
3
-1 1 2
-1 -1 3
-1 -1 -1

Sample Output

4