#include<stdio.h>

#define maxn 15
#define INF (1<<29)

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

int n;
int C[maxn][maxn],D[maxn][1<<12];

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

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

int solve ( int nod , int conf ){
	if ( D[nod][conf] != INF )	return D[nod][conf];
	
	int nr = 0; int c[maxn],pozi;
	for ( int i = 0 ; i < n ; ++i ){
		if ( conf & (1<<i) ){
			c[nr++] = i;
			if ( i == nod )
				pozi = nr-1;
		}
	}
	
	if ( nr == 1 ){
		D[nod][conf] = 0;
		return 0;
	}
	
	for ( int i = 0 ; i < nr ; ++i ){
		if ( c[i] != nod ){
			D[nod][conf] = min(D[nod][conf],solve(c[i],conf^(1<<nod)) + C[nod][c[i]]);
		}
	}
	
	for ( int i = 1 ; i < (1<<nr) ; ++i ){
		if ( i & (1<<pozi) )	continue ;
		
		int new_conf = conf;
		for ( int j = 0 ; j < nr ; ++j ){
			if ( i & (1<<j) )
				new_conf ^= (1<<c[j]);
		}
		
		for ( int j = 0 ; j < nr ; ++j ){
			if ( i & (1<<j) ){
				int now = max(solve(c[j],conf ^ new_conf),solve(nod,new_conf)) + C[nod][c[j]];
				D[nod][conf] = min(D[nod][conf],now);
			}
		}
	}
	
	return D[nod][conf];
}

int main () {
	
	int t;
	fscanf(f,"%d",&t);
	
	for ( int ii = 1 ; ii <= t ; ++ii ){
		
		fscanf(f,"%d",&n);
		for ( int i = 0 ; i < n ; ++i ){
			for ( int j = 0 ; j < n ; ++j ){
				fscanf(f,"%d",&C[i][j]);
			}
		}
		
		for ( int i = 0 ; i < n ; ++i ){
			for ( int j = 0 ; j < (1<<n) ; ++j ){
				D[i][j] = INF;
			}
		}
		
		fprintf(g,"%d\n",solve(0,(1<<n)-1));
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}