#include <stdio.h>
#include <vector>
using namespace std;

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)


int A[MAXN][MAXN];

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

vector <int> V[1 << MAXN];


void g(void) 
{
	for (int i = 1; i < 1 << MAXN; ++ i)
		for (int j = 0; j < MAXN; ++ j)
			if ((i >> j) & 1)
				V[i].push_back(j);
}

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

	int a[MAXN], cnt = 0, ret = INF;

	for (int i = (int)(V[s].size()); i --; )
		if (V[s][i]  != up)
			a[cnt ++] = V[s][i];

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

int solve(const 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(n, 0, (1 << n) - 1);
}

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

	int n;

	g();
	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(n));
	}
	fcloseall();

	return 0;
}