#include <cstdio>
#include <cstring>

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

const int INF=2000000000;

int t[14][1<<14];

int mat[14][14];

int n;

int max(const int &a, const int &b)
{
	return a>b?a:b;
}
int min(const int &a, const int &b)
{
	return a<b?a:b;
}

int log[1<<13];

void main2()
{
	fscanf(in,"%d",&n);

	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			fscanf(in,"%d",&mat[i][j]);
		}
	}

	for(int a=0; a<12; a++)
	{
		for(int i=1; i<=(1<<n); i++)
		{
			t[a][i]=INF;
		}
	}

	for(int i=1; i<(1<<n); i++)
	{
		int nre=0;

		int auxi;

		auxi=i;

		while(auxi)
		{
			nre++;
			auxi-=auxi&(-auxi);
		}
		/*
		for(int a=0; a<n; a++)
		{
			if(i&(1<<a))
			{
				nre++;
			}
		}
*/
		if(nre==1)
		{
			for(int a=0; a<n; a++)
			{
				if(i&(1<<a))
				{
					t[a][i]=0;
				}
			}
			continue;
		}

		auxi=i;

		while(auxi)
		{
			int a=auxi&(-auxi);
			auxi-=a;
			a=log[a];

			for(int j=1; j<1<<(nre-1); j++)
			{
				int m1=0,m2=0;
				int cnt=0;

				int aux2;

				aux2=i;

				while(aux2)
				{
					int f=aux2&(-aux2);
					aux2-=f;
					f=log[f];
					if(f!=a)
					{
						if(j&(1<<cnt))
						{
							m1+=1<<f;
						}
						cnt++;
					}
				}
				m2=i-m1;

				aux2=m1;

				while(aux2)
				{
					int f=aux2&(-aux2);
					aux2-=f;
					f=log[f];
					t[a][i]=min(t[a][i],mat[a][f]+max(t[a][m2],t[f][m1]));
				}
			}
		}
	}

	fprintf(out,"%d\n",t[0][(1<<n)-1 ]);

}

int main()
{
	for(int i=0; i<12; i++)
	{
		log[1<<i]=i;
	}

	int t;

	fscanf(in,"%d",&t);

	while(t)
	{
		t--;
		main2();
	}


    return 0;
}