#include <cstdio>
#include <cstring>
#define maxn 14
#define inf 2000000000

using namespace std;

int n, m, i, j, t;
int cs[maxn][maxn];
int a[maxn][1 << maxn], viz[maxn][1 << maxn];

void init() {
	memset(cs, 0, sizeof(cs));
	memset(a, 0xf, sizeof(a));
	memset(viz, 0, sizeof(viz));
}

inline int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int solve(int nod, int mask) {
	int i, j, m1, m2, k, rez, newm, sz, fin;
	int s[maxn];
	
	if (viz[nod][mask] == 1)
		return a[nod][mask];
	
	viz[nod][mask] = 1;
	
	memset(s, 0, sizeof(s));
	sz = -1;
	for (i = 0; i < n; i++) 
		if ((mask & (1 << i))) {
			sz++;
			s[sz] = i;
		}
	sz++;
	
	//din S o sa aleg atat nodul urmator cat si configuratia care vine
	fin = 0;
	for (i = 0; i < n; i++)
		fin += cs[nod][i];
	for (i = 1; i < (1 << sz); i++) {		
		newm = 0;
		for (j = 0; j < sz; j++)
			if (i & (1 << j))
				newm += (1 << s[j]);
		if ((newm & (1 << nod)) == 0) {
			rez = 0;
			m2 = solve(nod, mask - newm);
			
			for (j = 0; j < sz; j++) {
				if (newm & (1 << s[j])) {
					m1 = solve(s[j], newm);
					rez = max(m1, m2);
					
					if (rez + cs[nod][s[j]] < fin)
						fin = rez + cs[nod][s[j]];
				}
			}
		}
	}
	if (sz == 1)
		fin = cs[nod][s[0]];
	a[nod][mask] = fin;
	return fin;
}

int main() {
	freopen("cast.in", "r", stdin);
	freopen("cast.out", "w", stdout);
	
	scanf("%d", &t);
	
	for (; t > 0; t--) {
		scanf("%d", &n);
		
		init();
		
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				scanf("%d", &cs[i - 1][j - 1]);
			
		viz[0][0] = 1;
		a[0][0] = 0;
		
		printf("%d\n", solve(0, (1 << n) - 1));
			
	}
	
	return 0;
}