# include <stdio.h>

# define  _fin  "cast.in"
# define  _fout "cast.out"

# define  maxn	13
# define  inf	1000000000
# define  conf	4114


int t[maxn][conf], c[maxn][maxn], n;

int i, j, s, to, s2, to2, as2, bl[maxn];

int A, B;
# define	min(a,b)	((A=(a))<(B=(b)) ? A : B)
int C, D;
# define	max(c,d)	((C=(c))>(D=(d)) ? C : D)

int p2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192};

void solve()
{
	for (s=1, to=p2[n]-1; s<=to; ++s)
		for (i=1; i<=n; ++i)
			if ( s & p2[i-1] && t[i][s] == inf ) {
				for (bl[0]=0, j=1; j<=n; ++j)
					if ( s & p2[j-1] ) bl[++bl[0]] = j;
				
				for (s2=1, to2=p2[bl[0]]-1; s2<=to2; ++s2) {
					// build the actually s2
					for (as2=0, j=1; j<=bl[0]; ++j)
						if ( s2 & p2[j-1] )
							as2 |= p2[bl[j]-1];
					
					if ( as2==s ) continue;

					for (j=1; j<=n; ++j) {
						if ( i==j ) continue;
						if ( as2 & p2[j-1] )
							t[i][s] = min(t[i][s], c[i][j] + max(t[j][as2],t[i][s^as2]) );
					}
				}
			}
}

int main()
{
	freopen(_fin, "r", stdin);
	freopen(_fout,"w", stdout);
	
	int nt;
	for (scanf("%d", &nt); nt; --nt) {
		for (scanf("%d", &n), i=1; i<=n; ++i)
			for (j=1; j<=n; ++j) scanf("%d", &c[i][j]);
		
		for (i=0; i<maxn; ++i) for (j=0; j<conf; ++j) t[i][j] = inf;
		for (i=1; i<=n; ++i) t[i][1<<(i-1)] = 0;
		
		solve();
		
		printf("%d\n", t[1][(1<<n)-1]);
	}
	
	return 0;
}