#include<iostream>
#include<string>

using namespace std;

#define nm 13
#define nconf 4100
#define inf 2000000000

int timp[nm][nm],tmin[nm][nconf];
int t,n;

inline void reinit()
{
    int i,j;   
       
    for(i=1;i<=n;i++) 
      for(j=0;j<(1<<n);j++)
        tmin[i][j]=-1;
        
    for(i=1;i<=n;i++)    
      tmin[i][(1<<(i-1))]=0;
}

void memo(int nod,int config)
{
     int alpha[nm],dim=0,i,j,k;
     
     if(tmin[nod][config]>=0) return ;
     
     for(i=0;i<n;i++)
       if(((1<<i)&config) && (i+1!=nod))
         alpha[++dim]=i+1;
       
     
     int best=inf;
     
     for(i=1;i<=dim;++i)
     { 
       int nnod=alpha[i];
       
       for(j=0;j<(1<<dim);++j)
       {
         int nconfig=0,lconfig=0;
         
         for(k=0;k<dim;++k)
           if(((1<<k)&j) || (k+1==i))
              nconfig+=(1<<(alpha[k+1]-1));
         
         for(k=0;k<n;++k)
           if(((1<<k)&config)&&!((1<<k)&nconfig))     
             lconfig+=(1<<k);
         
         memo(nnod,nconfig);
         memo(nod,lconfig);
         
         best=min(best,max(tmin[nod][lconfig],tmin[nnod][nconfig])+timp[nod][nnod]);     
       }
       
     }  
     
     tmin[nod][config]=best;
}

int main()
{
    int i,j;
    
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);
    
    scanf("%d",&t);
    
    while(t--)
    {
      scanf("%d",&n);
      
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          scanf("%d",&timp[i][j]);
          
      //reinit();    
      memset(tmin,-1,sizeof(tmin));
      
      for(i=1;i<=n;i++)    
      tmin[i][(1<<(i-1))]=0;
      
      memo(1,(1<<n)-1);
      
      printf("%d\n",tmin[1][((1<<n)-1)]);
    }
    
    return 0;
}