#include <stdio.h>

#define NMAX 13
#define INF 1000000000

int A[NMAX][NMAX];
int T[NMAX][1 << NMAX];
int state[NMAX], state2[NMAX];
int i, j, k, N, nones, ntwos, s, s2, t;

void generateStates2(int n)
{
	if (n >= N)
	{
		if (ntwos == nones)
			return;

		s2 = 0;
		for (i = 0; i < N; i++)
			if (state2[i] == 1)
				s2 |= (1 << i);

		for (i = 0; i < N; i++)
			if (state[i] == 1 && state2[i] == 0)
				for (j = 0; j < N; j++)
					if (state2[j] == 1)
					{
						if (T[j][s2] > T[i][s - s2])
							t = T[j][s2];
						else
							t = T[i][s - s2];

						if (t + A[i][j] < T[i][s])
							T[i][s] = t + A[i][j];
					}
	}
	else
	{
		if (state[n] == 0)
		{
			state2[n] = 0;
			generateStates2(n + 1);
		}
		else
		{
			state2[n] = 0;
			generateStates2(n + 1);

			state2[n] = 1;
			ntwos++;
			generateStates2(n + 1);
			ntwos--;
		}
	}
}

void generateStates(int n)
{
	if (n >= N)
	{
		s = 0;
		for (i = 0; i < N; i++)
			if (state[i] == 1)
				s |= (1 << i);

		for (i = 0; i < N; i++)
			T[i][s] = INF;

		if (nones == 1)
		{
			for (i = 0; i < N; i++)
				if (state[i] == 1)
					T[i][s] = 0;
		}
		else
		if (nones > 1)
		{
			ntwos = 0;
			generateStates2(0);
		}
	}
	else
	{
		state[n] = 0;
		generateStates(n + 1);

		state[n] = 1;
		nones++;
		generateStates(n + 1);
		nones--;
	}
}

int main()
{
	int nt;

	freopen("cast.in", "r", stdin);
	freopen("cast.out", "w", stdout);

	scanf("%d", &nt);

	while (nt--)
	{
		scanf("%d", &N);

		for (i = 0; i < N; i++)
			for (j = 0; j < N; j++)
				scanf("%d", &A[i][j]);

		nones = 0;
		generateStates(0);

		printf("%d\n", T[0][(1 << N) - 1]);
		fprintf(stderr, "%d\n", T[0][(1 << N) - 1]);
	}

	return 0;
}