#include <cstdio>
#include <cstring>

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

const int INF=2000000000;

int t[12][1<<12];

int mat[12][12];

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;
}

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;
		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;
		}

		for(int a=0; a<n; a++)
		{
			if(i&(1<<a))
			{
				for(int j=1; j<1<<(nre-1); j++)
				{
					int m1=0,m2=0;
					int cnt=0;

					for(int f=0; f<n; f++)
					{
						if(i&(1<<f) && f!=a)
						{
							if(j&(1<<cnt))
							{
								m1+=1<<f;
							}
							cnt++;
						}
					}
					m2=i-m1;

					for(int f=0; f<n; f++)
					{
						if(m1&(1<<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()
{
	int t;

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

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


    return 0;
}