#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <array>
using namespace std;

using timp_t = int16_t;
using mask_t = uint16_t;
constexpr timp_t timp_inf = 20000;
constexpr int maxn = 12;

int popcount(int x){
	int rez = 0;
	for( ; x; x ^= x&-x, ++rez);
	return rez; }

void do_test(ifstream& f, ofstream& g){
	int n;
	f >> n;

	array<array<timp_t, maxn>, maxn> t;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			f >> t[i][j]; } }

	array<array<timp_t, maxn>, 1<<maxn> d = {};
	for(auto& x : d){
		for(auto& y : x){
			y = timp_inf; } }

	for(mask_t mask = 1; mask < 1<<n; ++mask){
		if(popcount(mask) == 1){
			d[mask][log2(mask)] = 0;
			continue; }

		for(int i = 0; i < n; ++i){
			if(((mask>>i)&1) == 0){
				continue; }

			mask_t mask_left = mask ^ (1<<i);

			for(mask_t submask = mask_left; submask; submask = (submask-1)&mask_left){
				for(int j = 0; j < n; ++j){
					if(((submask>>j)&1) == 0){
						continue; }
					d[mask][i] = min<timp_t>(d[mask][i], t[i][j] + max(d[submask][j], d[mask^submask][i])); } } } }
	g << d[(1<<n)-1][0] << '\n'; }

int main(){
	ifstream f("cast.in");
	ofstream g("cast.out");
	int t;
	f >> t;
	for(int i = 0; i < t; ++i){
		do_test(f, g); }
	return 0; }