// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define err(...) fprintf(stderr, __VA_ARGS__)
using ll=long long;
using dbl=long double;
constexpr int NMAX=12;
constexpr ll MOD=1'000'000'007;

int N;
int d[NMAX][NMAX];
int dp[1<<NMAX][NMAX];

int solve()
{
	int mask, submask, i, j, maxMask=1<<N;

	for(mask=0;mask<maxMask;++mask)
		for(i=0;i<N;++i)
			dp[mask][i]=MOD;
	for(i=0;i<N;++i)
		dp[1<<i][i]=0;

	for(mask=3;mask<maxMask;++mask)
		for(i=0;i<N;++i)
			if(mask&(1<<i))
				for(submask=mask&(mask-1);submask;submask=mask&(submask-1))
					for(j=0;j<N;++j)
						if(submask&(1<<j))
							dp[mask][i]=std::min(dp[mask][i], d[i][j]+std::max(dp[submask][j], dp[mask^submask][i]));

	return dp[maxMask-1][0];
}

int main()
{
	FILE* f=fopen("cast.in", "r"), *g=fopen("cast.out", "w");
	int _, i, j;

	fscanf(f, "%d", &_);
	do
	{
		fscanf(f, "%d", &N);
		for(i=0;i<N;++i)
			for(j=0;j<N;++j)
				fscanf(f, "%d", d[i]+j);

		fprintf(g, "%d\n", solve());
	}while(--_);

	fclose(f);
	fclose(g);
	return 0;
}