//题目要求：给出每两个村庄之间的距离矩阵，将所有村庄连接起来且总长度最短，输出连接村庄后最长的那条路
//也就是构建最小生成树求生成树里最长的一条边
#include <iostream>

using namespace std;

int n;             //村庄数
int G[505][505];   //邻接矩阵
int inTree[505];   //节点是否已经在生成树里
int distances[505];//节点到生成树最短距离

int Prim() {
	int maxLen = 0;
	inTree[1] = 1;                       //先把第一个节点加入生成树
	for (int i = 1; i <= n; i++) {
		distances[i] = G[1][i];      //更新最短距离数组
	}
	for (int k = 0; k < n - 1; k++) {  //要把剩下n-1个节点加入到生成树里
		int tempLen = 70000;  //随便找个比题目给出的距离最大值还大的数
		int tempIndex = -1;
		for (int m = 1; m <= n; m++) {
			if (!inTree[m] && distances[m] < tempLen) {  //找出不在生成树里的距离生成树最近的节点
				tempLen = distances[m];
				tempIndex = m;
			}
		}
		inTree[tempIndex] = 1;          //加入生成树
		if(maxLen < tempLen)            //用于更新生成树里最长的边
			maxLen = tempLen;
		for (int p = 1; p <= n; p++) {
			if (!inTree[p] && distances[p] > G[tempIndex][p])  //更新最短距离数组
				distances[p] = G[tempIndex][p];
		}
	}
	return maxLen;
}

int main()
{
	int cases = 0;
	cin >> cases;
	while (cases--) {
		cin >> n;
		memset(G, 0, sizeof(G));
		memset(inTree, 0, sizeof(inTree));
		memset(distances, 0, sizeof(distances));

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> G[i][j];
			}
		}

		int res = Prim();
		cout << res << endl;
	}
	return 0;
}