#include <fstream>
#include <cstring>
using namespace std;

const int kMaxN = 13, kMaxConf = 4100, kInfinity = 0x3f3f3f3f;

ifstream fin("cast.in");
ofstream fout("cast.out");

int T, N, dist[kMaxN][kMaxN], dp[kMaxN][kMaxConf];

int Sol(int root, int conf) {
	if (dp[root][conf] == kInfinity) {
		for (int first = 0; first < N; ++first)
			if (conf & (1 << first) && first != root) {
				dp[root][conf] = min(dp[root][conf], Sol(root, conf ^ (1 << first)) + dist[root][first]);
				int rem = conf ^ (1 << root) ^ (1 << first);
				for (int i = rem; i; i = (i - 1) & rem) {
					int nw = i | (1 << first);
					dp[root][conf] = min(dp[root][conf], max(Sol(first, nw), Sol(root, conf ^ nw)) + dist[root][first]);
				}
			}
	}
	return dp[root][conf];
}

int main() {
	fin >> T;
	while (T--) {
		fin >> N;
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < N; ++j)
				fin >> dist[i][j];
		memset(dp, kInfinity, sizeof dp);
		for(int i = 0; i < N; ++i)
			dp[i][1 << i] = 0;
		fout << Sol(0, (1 << N) - 1) << "\n";
	}
	return 0;
}