#include <stdio.h>

const char iname[] = "cast.in";
const char oname[] = "cast.out";

#define MAXN 12

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define INF  int(1e9)

#define BIT(x, i) ((x) & (1 << (i)))


int ans[MAXN][1 << MAXN];


int f(int A[][MAXN], int n, int up, int s)
{
	if (ans[up][s] < INF)
		return  ans[up][s];

	int a[MAXN], cnt, ret = INF;
	
	for (int i = cnt = 0; i < n; ++ i)
		if ((i != up) && BIT(s, i))
			a[cnt ++] = i;

	for (int r = 1; r < 1 << cnt; ++ r) {
		int  t;
		for (int i = t = 0; i < cnt; ++ i)
			if (BIT(r, i))
				t |= 1 << a[i];
		
		int x = f(A, n, up, s ^ t);
		for (int i = 0; i < cnt; ++ i)
			if (BIT(r, i)) {
				int aux = A[up][a[i]] + MAX(x, f(A, n, a[i], t));
				if (ret > aux)
					ret = aux;
			}
	}
	return ans[up][s] = ret;
}

int solve(int A[][MAXN], int n)
{
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < 1 << n; ++ j)
			ans[i][j] = INF;
		ans[i][1 << i] = 0;
	}
	return f(A, n, 0, (1 << n) - 1);
}

int main(void)
{
	FILE *fi = fopen(iname, "r");
	FILE *fo = fopen(oname, "w");
	int cnt;

	int A[MAXN][MAXN], n;

	for (fscanf(fi, "%d", &cnt); cnt > 0; -- cnt) {
		fscanf(fi, "%d", &n);
		for (int i = 0; i < n; ++ i)
			for (int j = 0; j < n; ++ j)
				fscanf(fi, "%d", &A[i][j]);
		fprintf(fo, "%d\n", solve(A, n));
	}
	fcloseall();

	return 0;
}