#include "stdio.h"
#include "string.h"
#define max 501
#define INF 999999
int road[max][max];
int n;
void init()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
			road[i][j]=0;
			else
			road[i][j]=INF;
}
int main()
{
	int i,j,sum,k,rec,len,dist[max],s[max],temp,t;
	int cases;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%d",&n);
		init();
		for(i=1;i<=n;i++)
		  for(j=1;j<=n;j++)
			{
				scanf("%d",&len);
				if(len<road[i][j])
					road[i][j]=len;
			}
		  sum=0;
		  for(i=1;i<=n;i++)
		   dist[i]=road[1][i];
		  memset(s,0,sizeof(s));
		  s[1]=1;
			for(i=2;i<=n;i++)
			{ 
                 temp=INF;
				 rec=-1;
				for(j=1;j<=n;j++)
				if(!s[j]&&dist[j]<temp)
				{
					temp=dist[j];
					rec=j;
				}
				s[rec]=1;
				for(k=1;k<=n;k++)
				if(!s[k]&&road[rec][k]<dist[k])
				dist[k]=road[rec][k];
			}
			t=0;
			for(i=1;i<=n;i++)
				if(t<dist[i])
					t=dist[i];
				printf("%d\n",t);
	}
	return 1;
}