#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

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

int x;
int adj[12][12];
int dp[12][1<<12];

int sol(int k, int mask) {
	//std::cout << k << " " << mask << "\n";

	if (!(mask&(1<<k))) return 0x3f3f3f3f;
	if (__builtin_popcount(mask)==1) return 0;
	if (dp[k][mask]!=-1) return dp[k][mask];

	dp[k][mask] = 0x3f3f3f3f;
	for (int new_mask = mask; new_mask; new_mask = mask&(new_mask-1)) {
		if (new_mask&(1<<k)) {
			continue;
		}
		for (int new_k = 0; new_k < x; new_k++) {
			if (new_mask&(1<<new_k)) {
				int cand = std::max(sol(new_k,new_mask),sol(k,mask^new_mask));
				dp[k][mask] = std::min(dp[k][mask],adj[k][new_k]+cand);
			}
		}
	}

	return dp[k][mask];
}

void test_case() {
	fin >> x;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < x; j++) {
			fin >> adj[i][j];
		}
	}

	memset(dp,-1,sizeof(dp));
	fout << sol(0,(1<<x)-1) << "\n";
}

int main() {
	int test_cases;
	fin >> test_cases;
	while (test_cases--) {
		test_case();
	}
}