题目描述

岛国Flatopia是完全平坦的。不幸的是，Flatopia没有公路,所以在Flatopia交通是很难的。Flatopian政府已经意识到这个问题。他们正计划修建一些公路，以便在不离开公路系统的情况下，在任何一对城镇之间行驶。

Flatopian城镇编号从1到N，每一条高速公路连接了两个城镇。所有的高速公路都遵循直线。所有公路均可双向使用。公路可以自由交叉，但驾驶员只能在位于两条公路末端的一个城镇的公路之间进行转换。

Flatopian政府想要减少最长的公路长度要建。然而，他们想保证每个城镇都可以从其他城镇到达公路。

输入格式

输入的第一行是一个整数t，它告诉多少个测试用例。

每一个案例的第一行是一个整数$\red{n（3 < N = n = 500）}$，这是村庄的数目。接下来的N行，其中第i个包含N个整数，而这些N整数j的距离（距离应该是一个整数，在$\red{[1，65536]}$ 区间）村庄i，j有每个测试一个空行之间。

输出格式

对于每一个测试用例，你应该输出一行包含一个整数，这是最

长的道路要建的长度，使所有村庄连接，这个值是最低的。

样例

输入样例

1
3
0 990 692
990 0 179
692 179 0

输入样例

692