#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> G[1 << MAXN], 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);

	for (int i = 1; i < 1 << MAXN; ++ i)
		for (int j = 1; j < 1 << MAXN; ++ j)
			if ((i & j) == j)
				G[i].push_back(j);
}

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

	int ret = INF;

	for (int i = (int)(G[s].size()); i --; ) {
		int  r = G[s][i];
		if ((r >> up) & 1)
			continue ;
		for (int j = (int)(V[r].size()); j --; ) {
			int tmp = A[up][V[r][j]] + MAX(f(n, up, s ^ r), f(n, V[r][j], r));
			if (ret > tmp)
				ret = tmp;
		}
	}

	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;
}