#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N = 14;
const int inf = 10000000;

int n, c[N][N], d[N][1<<N];

int din(int nod, int conf) {
	if(d[nod][conf] != inf)
		return d[nod][conf];
	
	vector<int> el;
	int i, j, confn;
	
	for(i = 0; i < n; ++i)
		if((conf & (1<<i)) && nod != i)
			el.push_back(i);
	
	for(i = 0; i < (1<<el.size()); ++i) {
		confn = 0;
		
		for(j = 0; j < el.size(); ++j)
			if(i & (1<<j))
				confn |= (1<<el[j]);
		
		for(j = 0; j < el.size(); ++j)
			if(i & (1<<j))
				d[nod][conf] = min(d[nod][conf], 
								   max(din(nod, conf ^ confn), din(el[j], confn)) + c[nod][el[j]]);
	}
	
	return d[nod][conf];
}

void solve() {
	int i, j;
	
	cin >> n;
	
	for(i = 0; i!=n; ++i)
		for(j = 0; j!=n; ++j)
			cin >> c[i][j];
	
	for(i = 0; i!=n; ++i) {
		for(j = 0; j < (1<<n); ++j)
			d[i][j] = inf;
		d[i][1<<i] = 0;
	}
	
	cout << din(0, (1<<n) - 1) << "\n";
}

int main() {
	int t;
	
	freopen("cast.in", "r", stdin);
	freopen("cast.out", "w", stdout);
	
	cin >> t;
	
	while(t--)
		solve();
	
	return 0;
}