公路
时限：1000MS 内存限制：65536K
提交材料共计： 33392 接受： 15129
描述
这个岛国的Flatopia是完全平坦的。不幸的是，Flatopia没有公共公路。因此，在Flatopia的交通很困难。在政府意识到了这个问题。他们正计划修建一些公路，以便在没有离开公路系统的情况下在任何一对城镇之间开车。
Flatopian镇从1到n。每条公路连接两个城镇。所有的公路都是直线。所有公路都可以双向使用。公路可以自由交叉，但司机只能在公路之间的一个城镇，位于两条高速公路的尽头。
在政府希望将最长的公路长度减少到最低限度。然而，他们希望保证每个城镇都是高速公路-从其他城镇都可以到达。
输入
输入的第一行是一个整数t，它告诉接下来有多少个测试用例。
每个情况的第一行是整数n(3<=n<=500)，这是村庄的数目。然后是n行，其中的i-th包含n个整数，而这些n个整数的j-是距离(距离应该是内[1，65536)的整数)。在村一和村j之间，每个测试用例后有一条空行。
输出
对于每个测试用例，您应该输出一个包含整数的行，这个整数是要构建的最长道路的长度，这样所有的村庄都连接起来，这个值是最小的。
样本输入
1
3
0 990 692
990 0 179
692 179 0
样本输出