#include <stdio.h>

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

#define MAXN 12

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

const int infinity = int(1e9);


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


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

	if (s == 0)
		return  infinity;
	else if ((s & (s - 1)) == 0) {
		for (int i = 0; i < n; ++ i)
			if ((s >> i) & 1)
				return  (ans[r][s] = A[r][i]);
	}

	int a[MAXN + 1];
	
	for (int i = a[0] = 0; i < n; ++ i)
		if ((s >> i) & 1)
			a[++ a[0]] = i;

	for (int st = 1; st < 1 << a[0]; ++ st) {
		int t = 0;
		for (int i = 0; i < a[0]; ++ i) {
			if ((st >> i) & 1)
				t |= 1 << a[i + 1];
		}
		int x = f(A, n, r, s ^ t);
		for (int i = 0; i < a[0]; ++ i) 
			if ((st >> i) & 1) {
				int j = a[i + 1];
				if (j == r)
					continue ;
				int y = f(A, n, j, t); 
				if (ans[r][s] > A[r][j] + MAX(x, y))
					ans[r][s] = A[r][j] + MAX(x, y);
			}
	}
	return ans[r][s];
}

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] = infinity;
		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;
}