# include <cstdio>
//# include <cstring>
# include <vector>

using namespace std;

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

# define max 12
# define maxV 1<<max
int c[max][max];
long d[max][maxV];
int n,i,T,j,nr;
long mask,mask2,k,nrp,mask1;
int p[max];
int s[max];
int aux;

# define minim(a,b) (a<b?a:b)
# define maxim(a,b) (a>b?a:b)

long calcmin()
{
     memset(d,1,sizeof(d));
     
     for(i=0;i<n;i++)
		 d[i][1<<i] = 0;
         
     for(mask = 1;mask < (1<<n);mask++)
     {
         for(i=0;i<n;i++)
         {
             if(mask&(1<<i))
			 {
                  aux = mask;
				  k=0,nr=0;
				  while(aux)
				  {
					  if(aux&1)
						  s[nr++] = k;
					  aux>>=1;
					  ++k;
				  }
                  
                 if(nr == 1)
                     continue;
                     
                 for(k=1;k<(1<<nr);++k)
				  {
					  aux = k;
					  j=0;
					  mask1=0;
					  nrp=0;
					  while(aux)
					  {
						  if(aux&1)
						  {
							  mask1 += 1<<(s[j]);
							  p[nrp++] = s[j];
						  }
						  aux>>=1;
						  ++j;
					  }					  
					  mask2 = mask-mask1;
					  for(j=0;j<nrp;++j)
						  d[i][mask] = minim(d[i][mask] , c[i][p[j]] + maxim( d[i][mask2] , d[p[j]][mask1] ));
				  }                     
             }
         }
     }
     
	 return d[0][(1<<n)-1];
}

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