#include <stdio.h>
#define NMAX 13
#define SMAX (1 << (NMAX-1)) + 5

long int Tmin[NMAX][SMAX],i,j,k,n,T,nrt;
long int a[NMAX][NMAX];

void citire()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
		scanf("%ld",&a[i][j]);
for (i=0;i<=n;i++)
	for (j=0;j<=(1 << n);j++)
                Tmin[i][j]=-1;
}

long int MAXX(long int a, long int b)
{
if (b>a) return b;
return a;
}

long int MINN(long int a, long int b)
{
if (a<b) return a;
return b;
}

void compute(long int rad, long int mult)
{
long int ok;
long int k,nr,v[NMAX],poz[NMAX],S1,S2,timp,rada,i;
if (Tmin[rad][mult]!=-1) return;

if (mult==(1 << (rad-1))) {Tmin[rad][mult]=0;return;}

k=mult;
nr=0;
while (k)
        {v[++nr]=k%2;
        k/=2;}
k=0;
for (i=1;i<=nr;i++)
	if (v[i]) {poz[++k]=i;v[i]=0;
		  if (i==rad) rada=k;
		  }
v[k]=0;
timp=-5;
ok=0;
long int T,T1,T2;
while (!ok)
        {
        for (i=1;v[i]==1;i++)
                 v[i]=0;
	v[i]++;
	if (!v[rada]) {
                     S2=0;S1=0;
                     for (i=1;i<=k;i++)
			if (v[i]) S1=S1 + (1 << (poz[i]-1));
				else S2=S2 + (1 << (poz[i]-1));
                     for (i=1;i<=k;i++)
                        if (v[i]) {
				  if (Tmin[poz[i]][S1]==-1) compute(poz[i],S1);
				  if (Tmin[rad][S2]==-1) compute(rad,S2);
				  T1=Tmin[poz[i]][S1];T2=Tmin[rad][S2];
				  T=a[rad][poz[i]]+MAXX(T1,T2);
                                  if (timp==-5) timp=T;
					else timp=MINN(T,timp);
                                  }
                     }
        ok=1;
        for (i=1;i<=k;i++)
                if (v[i]==0) {ok=0;break;}
        }
Tmin[rad][mult]=timp;
}



void solve()
{
long int S;
S=(1 << n)-1;
compute(1,S);
printf("%ld\n",Tmin[1][S]);
}

int main()
{
freopen("cast.in","r",stdin);
freopen("cast.out","w",stdout);
scanf("%ld",&T);
for (nrt=1;nrt<=T;nrt++)
{
citire();
solve();
}
return 0;
}