#include <fstream>
#include <algorithm>
#define DIM 15
#define INF 2000000005
#define infile "cast.in"
#define outfile "cast.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int n, t;

int cost[DIM][DIM], dp[DIM][1 << DIM];

int solve(int elem, int config) {
	if (dp[elem][config] != INF)
		return dp[elem][config];

	int res = INF;
	for (int new_elem = 0; new_elem < n; ++new_elem) {
		if (!(config & (1 << new_elem)) || new_elem == elem)
			continue;

		res = std::min(res, cost[elem][new_elem] + solve(elem, config ^ (1 << new_elem)));

		int temp = (config ^ (1 << elem) ^ (1 << new_elem));
		for (int old_config = temp; old_config; (--old_config) &= temp)
			res = std::min(res, cost[elem][new_elem] + std::max(solve(elem, config ^ old_config ^ (1 << new_elem)), solve(new_elem, old_config ^ (1 << new_elem))));
	}

	dp[elem][config] = res;

	return res;

}

int main() {
	f >> t;

	for (; t; --t) {
		f >> n;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				f >> cost[i][j];

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < (1 << n); ++j)
				dp[i][j] = INF;
			dp[i][1 << i] = 0;
		}

		g << solve(1, (1 << n) - 1) << "\n";
	}

	return 0;
}

//Trust me, I'm the Doctor!