Flatopia岛国是非常平坦的。不幸的是，Flatopia没有公路。所以Flatopia国的交通十分困难。该flatopian政府意识到这个问题。他们计划建设公路，使任意两个城镇都可以有公路连通。
flatopian城镇的编号从1到N，每条公路连接两个城镇，所有公路都是直线连接，且高速公路都是双向的，公路可以相互交叉，但司机只有在城镇中才能由一个公路转换到另一个公路。该flatopian政府想要减少最长的公路长度，但要保证每个镇都可以到达其他城镇。

注意，对于任意两村庄 u/v，u 到 v 的距离不一定等于 v 到 u 的距离！

输入的第一行是一个整数t，表示测试用例。
每个用例的第一行是一个整数N（3≤n≤500），这是村庄的数量。接下来的N行，其中第i个包含N个整数，以及这些N个整数的第j个数表示第i个村庄到第j个村庄的距离（距离应该是一个整数，范围是[ 1，65536 ]）。每个测试用例后有一个空行。

对于每个测试用例，输出一行包含一个整数，表示所有的村庄之间的道路的最长长度，并且这个值是最小的。