#include <iostream>
#include <string.h>

using namespace std;

int n;             //村庄数
int G[505][505];   //邻接矩阵
int dSet[505];     //连通分量数组，用于判断节点(村庄)是否在同一连通分量里

int Kruskal() {
	int maxLen = 0;
	for (int k = 0; k < n - 1; k++) {  //n个节点的最小生成树有n-1条边，每次连接一条边共需n-1次循环
		int minLen = INT_MAX;  //初始最短边长定为最大值
		int minV1 = 0;
		int minV2 = 0;
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j <= n; j++){                   //目标:遍历邻接矩阵找出全图最短边
                		if(dSet[i] != dSet[j] && G[i][j] < minLen){  //若两个节点不在同一连通分量且比当前找到的最短边还短
                    			minLen = G[i][j];                        //更新最短边，记录节点序号
                    			minV1 = i;
                    			minV2 = j;
                		}
            		}
		}

		for(int i = 1; i <= n; i++){
            		if(dSet[i] == dSet[minV2] && i != minV2)      //遍历dSet数组，将两个连通分量合为一个
                		dSet[i] = dSet[minV1];                    //即两个分量中的所有节点分量序号统一成一个值
		}
		dSet[minV2] = dSet[minV1];

        	if(maxLen < minLen)            //用于更新生成树里最长的边
			maxLen = minLen;
	}
	return maxLen;
}

int main()
{
	int cases = 0;
	cin >> cases;
	while (cases--) {
		cin >> n;
		memset(G, 0, sizeof(G));
		for(int i = 1 ; i <= n; i++)
            		dSet[i] = i;                   //初始化连通分量数组，初始时每个节点是一个单独的连通分量

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> G[i][j];
			}
		}
		int res = Kruskal();
		cout << res << endl;
	}
	return 0;
}