#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 12

int T, N, x[MAXN][MAXN];
int MIN[1 << MAXN][MAXN];

inline int MAX( int a, int b )
{
	return (a > b) ? a : b;
}

inline int getsol( int st, int k )
{
	if ( MIN[st][k] != 0x3f3f3f3f )
		return MIN[st][k];

	vector<int> stare;
	for (int i = 0; i < N; i++)
		if (i != k && (st & (1 << i)))
			stare.push_back(i);

	for (int nst = 0; nst < (1 << stare.size()); nst++)
	{
		int _st = 0;
		for (size_t i = 0; i < stare.size(); i++)
			if (nst & (1 << i))
				_st |= (1 << stare[i]);

		for (size_t i = 0; i < stare.size(); i++)
		{
			if ( !(_st & (1 << stare[i])) )
				continue;

			int val = x[k][ stare[i] ] + MAX( getsol( st ^ _st, k ), getsol( _st, stare[i] ) );
			if (val < MIN[st][k])
				MIN[st][k] = val;
		}
	}
	return MIN[st][k];
}

int main()
{
	freopen("cast.in", "rt", stdin);
	freopen("cast.out", "wt", stdout);
	
	for (scanf("%d", &T); T; T--)
	{
		scanf("%d", &N);
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				scanf("%d", x[i] + j);

		memset( MIN, 0x3f, sizeof(MIN) );
		for (int i = 0; i < N; i++)
			MIN[ 1 << i ][i] = 0;

		printf("%d\n", getsol( (1 << N) - 1, 0 ));
	}
	
	return 0;
}