#include <stdio.h>
#include <algorithm>

using namespace std;

#define pt(i) (1<<(i))
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define nmax 12
#define inf 1000111000

int H[nmax][1<<nmax],n,A[nmax][nmax],T,last[1<<nmax];

void doit(int i,int mask1,int mask2)
{
	if(i==n)
	{
		int j,aux1=mask1,aux2=mask2;
		if(!mask1||!mask2)
			return ;
		for(aux1=mask1;aux1;aux1&=aux1-1)
			for(aux2=mask2;aux2;aux2&=aux2-1)
			{
				i=last[aux1];
				j=last[aux2];
				H[i][mask1|mask2]=min(H[i][mask1|mask2],A[i][j]+max(H[i][mask1],H[j][mask2])),
				H[j][mask1|mask2]=min(H[j][mask1|mask2],A[j][i]+max(H[j][mask2],H[i][mask1]));
			}

		return ;
	}
	doit(i+1,mask1,mask2);
	doit(i+1,mask1|pt(i),mask2);
	doit(i+1,mask1,pt(i)|mask2);
}

int main()
{
	freopen("cast.in","r",stdin);
	freopen("cast.out","w",stdout);
	int ii,i,j;
	scanf("%d",&T);
	FOR(i,1,pt(12)) FOR(j,0,12)
		if(i&pt(j))
		{
			last[i]=j;
			break;
		}
	FOR(ii,0,T)
	{
		scanf("%d",&n);
		FOR(i,0,n) FOR(j,0,n)
			scanf("%d",&A[i][j]);
		FOR(i,0,n) FOR(j,0,pt(n))
			H[i][j]=inf;
		FOR(i,0,n)
			H[i][pt(i)]=0;
		doit(0,0,0);
		printf("%d\n",H[0][pt(n)-1]);

	}
	return 0;
}