#include <stdio.h>
#include <string.h>

#define NMAX 14
#define SHIFTN (1<<NMAX)
#define INFI 0x3f3f3f3f

int n;
int cost[NMAX][NMAX];
int min[NMAX][SHIFTN];
short uz[NMAX][SHIFTN];
//short nrbit[SHIFTN];

void read()
{
	int i, j;
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			scanf("%d", &cost[i][j]);
}

inline int MIN(int a, int b)
{
	return (a < b) ? (a) : (b);
}

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

int solve(int x, int conf)
{
	if(uz[x][conf])
		return min[x][conf];
	//if(nrbit[conf] == 1)
	//	return (min[x][conf] = 0);

	//printf("\n");
    //printf("%d %d\n", x, conf);

	++uz[x][conf];

	int others = conf - (1<<(x-1));
	int i, j;

	for(i = 1; i < (1<<n); ++i)
	{
		if((i & others) == i)
		{
               	       //printf("mere %d\n", i);
               	       for(j = 1; j <= n; ++j)
		       {
		           if(((i & (1 << (j-1))) > 0))
			       {
				       //printf("incerc cu %d\n", j);
				       min[x][conf] = MIN(min[x][conf], cost[x][j] + MAX(solve(j, i), solve(x, conf - i)));

				       //printf("x = %d, conf = %d, others = %d, i = %d, j = %d\n", x, conf, others, i, j);
				       //printf("%d\n", conf-i);
				       //printf("solve(j, i) = %d, solve(x, conf-i) = %d\n", solve(j, i), solve(x, conf-i));
				       //printf("\n"); 
				}
			}
		       
         }

	}

	return min[x][conf];
}

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

	int t;
	scanf("%d", &t);

	//for(int i = 1; i < SHIFTN; ++i)
	//	nrbit[i] = nrbit[i>>1] + (i&1);//, printf("%d %d\n", i, nrbit[i]);

	while(t--)
	{
		read();
		memset(uz, 0, sizeof(uz));
		memset(min, INFI, sizeof(uz));

		for(int i = 1; i <= n; ++i)
			min[i][1<<(i-1)] = 0, ++uz[i][1<<(i-1)];

		printf("%d\n", solve(1, (1<<n)-1));

        	//for(int i = 1; i <= n; ++i)
        	//{
           //     	for(int j = 1; j < (1<<n); ++j)
            //            	printf("%d ", min[i][j]);
            //    	printf("\n");
        	//}

	}
	return 0;
}