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

#define maxn 12
#define maxx 4096
#define maxv 1000000
#define max(a,b) (a > b ? a : b)

int n,x,y,r;
int a[maxn][maxn];
int c[maxn][maxx];

int F(int i,int j);

inline void back(int k)
{
     if (k==n)
     {
         if (x>0)
         {
            int a1=x,a2=y,a3=r,i,aux;
            for (i=0;i<n;i++)
              if (x&(1<<i)) 
              {
                  F(i,x);
                  x=a1,y=a2,r=a3;
                  F(r,y-x);
                  x=a1,y=a2,r=a3;
                  if (a[r][i]+max(c[r][y-x],c[i][x])<c[r][y]) c[r][y]=a[r][i]+max(c[r][y-x],c[i][x]);
              }
         }
     }
     else {
              back(k+1);
              if ((r!=k) && (y&(1<<k)))
              {
                    x+=1<<k;
                    back(k+1);
                    x-=1<<k;
              }
          }
}

int F(int i,int j)
{
    if (c[i][j]==-1)
    {
        c[i][j]=maxv;
        x=0,y=j,r=i;
        back(0);
    }
    return c[i][j];
}

int main()
{
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);
    
    int i,j,T;
    
    scanf("%d ",&T);
    
    while (T>0)
    {
          scanf("%d ",&n);
          for (i=0;i<n;i++)
            for (j=0;j<n;j++) scanf("%d ",&a[i][j]);
            
          memset(c,-1,sizeof(c));
          for (i=0;i<n;i++) c[i][1<<i]=0;
          
          printf("%d\n",F(0,(1<<n)-1));
            
          T--;
    }
    
    return 0;
}