#include<iostream>
#include <stdio.h>
#include<cmath> 
using namespace std;
int cmp(const void* a,const void* b)
{
	return *(int*)b-*(int*)a;
}


int prim(int a[][501],int n,bool s[])
{
	int lowcost[501];
	int closest[501];
	int maxle=0;
	s[1]=true;
	for(int i=2;i<=n;i++)
	{
		lowcost[i]=a[1][i];
		closest[i]=1;		//closest[j]表示J在S中的邻接顶点
		s[i]=false;              //false 表示尚未通过此顶点
		
	}///初始化过程
	
	for(i=1;i<n;i++)
	{
		int min=100000;
		int j=1;
		for(int k=2;k<=n;k++)
		{
			if(lowcost[k]<min && s[k]==false)
			{
				min=lowcost[k];
				j=k;
			}
		}
			s[j]=true;
			for(int e=2;e<=n;e++)
			{
				if(a[j][e]<lowcost[e] && s[e]==false)
				{
					lowcost[e]=a[j][e];
					closest[e]=j;
				}
			}
			
			
	}
	qsort(lowcost+1,n,sizeof(int),cmp);
	//for(i=1;i<n;i++)
		//cout<<lowcost[i]<<endl;
		
	return lowcost[1];

}



int main()
{
	int T;
	scanf("%d",&T);
	for(int i=0;i<T;i++)
	{
		int n;
		int a[501][501];
		bool s[501];
		memset(s,0,sizeof(s));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
					
		cout<<prim(a,n,s)<<endl;

	}
	return 0;
	
}