#include <cstdio>
#define inf 1<<30

int tt, n, a[15][15], v[15], c[15], d[15], l, u[15], poz, val, t[15][4100];

int max(int a, int b)
{
	if (a<b) a=b;
	return a;
}

void back(int p)
{
	int i, x=0, r;
	if (p>1)
	{
		for (i=1; i<p; i++) x+=1<<(v[d[i]]-1);
		for (i=1; i<p; i++)
		{
			r=a[v[poz]][v[d[i]]]+max(t[v[d[i]]][x], t[v[poz]][val-x]);
			if (r<t[v[poz]][val]) t[v[poz]][val]=r;
		}
	}
	for (i=d[p-1]+1; i<=l; i++)
		if (!u[i])
		{
			d[p]=i;
			u[i]=1;
			back(p+1);
			u[i]=0;
		}
}

int main()
{
	freopen("cast.in","r",stdin);
	freopen("cast.out","w",stdout);
	scanf("%d", &tt);
	int i, j, x, y;
	while (tt--)
	{
		scanf("%d", &n);
		for (i=1; i<=n; i++)
			for (j=1; j<=n; j++) scanf("%d",&a[i][j]);
		for (i=1; i<=n; i++)
			for (j=1; j<(1<<n); j++) t[i][j]=inf;
		for (i=1; i<(1<<n); i++)
		{
			x=i;
			l=0;
			for (j=1; j<=n; j++, x>>=1) 
			{
				c[j]=x&1;
				if (c[j]) v[++l]=j;
			}
			if (l==1) t[v[1]][i]=0; else
			for (j=1; j<=l; j++)
				{
					for (y=1; y<=n; y++) u[y]=0;
					u[j]=1;
					poz=j;
					val=i;
					back(1);
				}
		}
		printf("%d\n",t[1][(1<<n)-1]);
	}
}