# include <stdio.h>
# include <string>

using namespace std;

# define input "bcast.in"
# define output "bcast.out"

# define maxN 12
# define max 1<<maxN

int d[maxN][maxN],n,i,j,mask;
long Tm[maxN][max];

long mins(long x,long y)
{  return (x > y  ? y : x);  }

long maxs(long x,long y)
{  return (x > y  ? x : y);  }

long dettmin()
{
	 int k,nd,s[maxN],mask1,mask2,p[maxN],nrp;
	 memset(Tm,1,sizeof(Tm));

	 for(mask=1;mask<(1<<n);++mask)
		 for(i=1;i<=n;i++)
			 if((mask>>i-1)&1)
			 {
				  int aux = mask;
				  k=1,nd=0;
				  while(aux)
				  {
					  if(aux&1)
						  s[++nd] = k;
					  aux>>=1;
					  ++k;
				  }
				  if(nd==1)
				  {
					  Tm[i][mask] = 0;
					  continue;
				  }
				  for(k=1;k<(1<<nd);++k)
				  {
					  aux = k;
					  j=1;
					  mask1=0;
					  nrp=0;
					  while(aux)
					  {
						  if(aux&1)
						  {
							  mask1 += 1<<(s[j]-1);
							  p[++nrp] = s[j];
						  }
						  aux>>=1;
						  ++j;
					  }
					  mask2=mask-mask1;
					  for(j=1;j<=nrp;++j)
						  Tm[i][mask] = mins(Tm[i][mask] , d[i][p[j]] + maxs( Tm[i][mask2] , Tm[p[j]][mask1] ));
				  }
			 }
	 return Tm[1][(1 << n) - 1];
}

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);
    
    int T;   
    scanf("%d",&T);
    
    while(T)
    {
        scanf("%d",&n);    
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                 scanf("%d",&d[i][j]);
        
        printf("%ld\n",dettmin());
         
        T--;
    }
    
    return 0;    
}