#include<stdio.h>
using namespace std;
#define min(x,y) ( (x)<(y) ? (x) : (y) )
#define max(x,y) ( (x)>(y) ? (x) : (y) )
#define N 15
int n,c[N][N];
int a[N][4100],b[N][4100];
int s[N][4100];
inline void citire()
{
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
	{
		s[i][0]=0;
		for(int j=1; j<=n; ++j)
			scanf("%d",&c[i][j]);
	}
}
inline int nrb(int x)
{
	int cnt=0;
	while(x)
	{
		x&=x-1;
		++cnt;
	}
	return cnt;
}
inline void rezolva()
{
	for(int i=1,lim=1<<n,aux; i<lim; ++i)
	{
		aux=nrb(i);
		s[aux][++s[aux][0]]=i;
	}
	for(int i=1,aux=1; i<=n; ++i,aux<<=1)
	{
		b[i][0]=1;
		b[i][1]=aux;
	}
	int st,s1,s2;
	for(int t=2; t<=n; ++t)
	{
		for(int i=1; i<=n; ++i)
			b[i][4099]=b[i][0];
		for(int i=1,aux=1; i<=n; ++i,aux<<=1)
		{
			for(int w=1,lim=s[t][0]+1; w<lim; ++w)
			{
				if(!(s[t][w]&aux))
					continue;
				b[i][++b[i][0]]=s[t][w];
				st=s[t][w];
				a[i][st]=1<<30;
				for(int y=1,lim1=b[i][4099]+1; y<lim1; ++y)
				{
					if((b[i][y]|st)!=st)
						continue;
					s1=b[i][y];
					s2=st^s1;
					for(int j=1,aux1=1; j<=n; ++j,aux1<<=1)
					{
						if(!(s2&aux1))
							continue;
						a[i][st]=min(a[i][st],c[i][j]+max(a[i][s1],a[j][s2]));
					}
				}
			}
		}
	}
	printf("%d\n",a[1][s[n][1]]);
}
int main()
{
	freopen("cast.in","r",stdin);
	freopen("cast.out","w",stdout);
	int T;
	for(scanf("%d",&T); T; --T)
	{
		citire();
		rezolva();
	}
	return 0;
}