//cast 3^n cu cuplaj(am cam tractorit-o)

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

FILE*fin=fopen("cast.in","r");
FILE*fout=fopen("cast.out","w");

#define inf 1000000000
#define nm 20
#define min(a,b)((a)<(b)?(a):(b))

int a[nm][nm],viz[nm],t[nm],v1[nm],v2[nm],n,cd[nm];
int ans[(1<<12)],nrb[(1<<12)],s,d;
char cap[nm][nm],flow[nm][nm];

//bagi cuplaj intre m1 si m2

int bf()
{
  int i,j,nod;  
  
  for(i=0;i<=n+1;i++)
    viz[i]=0;
    
  cd[0]=1;
  cd[1]=s;  
  viz[s]=1;
  
  for(i=1;i<=cd[0];i++)
  {
    nod=cd[i];
    for(j=0;j<=n+1;j++)
      if(cap[nod][j]-flow[nod][j]&&!viz[j])
      {
        viz[j]=1;
        
        cd[0]++;
        cd[cd[0]]=j;
        t[j]=nod;
        
        if(j==d) return 1;
      }
  }
  return 0;
}

int cuplaj_maxim(int m1,int m2,int max_adm)
{
    int i,j,nod;
    
    memset(cap,0,sizeof(cap));
    memset(flow,0,sizeof(flow));
    
    //acuma formezi graful pt flux
    
    for(i=0;i<n;i++)
      if((1<<i)&m1) //inseamna ca calcul i e in multimea m1
      for(j=0;j<n;j++)
        if((1<<j)&m2) //inseamna ca calcul j e in multimea m2
          if(a[i][j]<=max_adm)
            cap[i][j]=1;
    //n e sursa, n+1 e destinatia
    
    for(i=0;i<n;i++)
    {
      if((1<<i)&m1) cap[n][i]=1;
      if((1<<i)&m2) cap[i][n+1]=1;
    }          
    
    //acuma bagi fluxul 
    
    s=n;d=n+1;
    int flux=0;
    
    while(bf())
    {
      nod=d;
      while(t[nod]!=s)
      {
        flow[t[nod]][nod]++;
        flow[nod][t[nod]]--;
        nod=t[nod];
      }
      
      flux++;
    }
    
    return flux;
}

int main()
{
  int tests,mask,i,j,d1,d2;  
  
  fscanf(fin,"%d",&tests);
  
  //vezi cati biti de unu are orice masca
  
  for(i=0;i<(1<<12);i++)      
    for(j=0;j<12;j++)
      if((1<<j)&i) nrb[i]++;
  
  while(tests--)
  {
                
    fscanf(fin,"%d",&n);
    
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        fscanf(fin,"%d",&a[i][j]);
        
    memset(ans,0x3f3f3f3f,sizeof(ans));
    ans[1]=0;
    
    
    for(mask=1;mask<(1<<n)-1;mask++)
    {
      //separi bitii de unu de cei de zero
      d1=0;
      d2=0;
      for(i=0;i<n;i++)
        if((1<<i)&mask)
        {
          v1[d1]=i;
          d1++;
        }  
        else 
        {
          v2[d2]=i;
          d2++;
        }
      
      //alegi o submultime spre care incerci sa transmiti informatia
      
      for(i=0;i<(1<<d2);i++)
        if(nrb[i]<=nrb[mask]) //verifici daca sunt suficiente calcuri transmitatoare
        {
          // multimea actualizata va fi mact
          
          int mact=0,m1=0,m2=0;
          
          for(j=0;j<d1;j++)
            m1+=(1<<(v1[j]));
            
          for(j=0;j<d2;j++)
            if(i&(1<<j))
              m2+=(1<<(v2[j]));  
          
          int st=0,dr=100000;    
          
          while(st<dr)
          {
            int mij=(st+dr)/2;
            if(cuplaj_maxim(m1,m2,mij)==nrb[i]) //daca se poate transmite informatia la toate
              dr=mij;
            else st=mij+1;  
          }
          
          mact=m1+m2;            
          
          ans[mact]=min(ans[mact],ans[mask]+st);
        }  
    }    
    fprintf(fout,"%d\n",ans[(1<<n)-1]);    
  }
  fclose(fin);
  fclose(fout);
  return 0;
}