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

using namespace std;

#define MAX_N 16    
#define MAX_P2 4096

int T;
int n, i, j, k, p, q;
int v[MAX_N], p2[MAX_N];
int d[MAX_N][MAX_N];
int c[MAX_N][MAX_P2];

void cit() {
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			scanf("%d", &d[i][j]);

	for (i = 0; i <= n; i++) p2[i] = 1 << i;
}

void solve() { 
	//initializare dinamica
	for (i = 0; i < p2[n]; i++)
		for (j = 1; j <= n; j++)
			c[j][i] = 2147000000;
	for (i = 1; i <= n; i++)
		c[i][1 << (i - 1)] = d[i][i];

    for (i = 0; i <= p2[n]; i++) {
		v[0] = 0;
		for (j = 0; j < n; j++)
			if ((i & p2[j]) != 0)
				v[++v[0]] = j + 1;

		for (j = 1; j < p2[v[0]] - 1; j++) {
			k = 0;
			for (p = 0; p < v[0]; p++)
				if ((p2[p] & j) != 0) k += p2[p];

			for (p = 1; p <= v[0]; p++)
				for (q = 1; q <= v[0]; q++)
					if (p != q && (p2[p - 1] & k == 0) && (p2[q - 1] & k == 0))
						c[v[p]][i] = min(c[v[p]][i], d[v[p]][v[q]] + max(c[v[q]][k], c[v[p]][i - k]));
		}
	}
}

int main() {
	freopen("cast.in", "r", stdin);
	freopen("cast.out", "w", stdout);
	
	scanf("%d", &T);

	while (T--) {
		cit();
		solve();
		printf("%d\n", c[1][(1 << n) - 1]);
	}

	return 0;
}