#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 k, int conf)
{
    if (uz[k][conf]) return min[k][conf];
    uz[k][conf] = 1;

    int u[NMAX];
    int i, j, nr = 0, cur, val, contra;
    int v1, v2;
    int best = INFI;

    for (i = 1; i <= n; ++i) if (i != k)
        if ((conf >> (i-1)) & 1) u[++nr] = i;
    if (nr == 0) return 0;

    for (i = 1; i <= ((1 << nr) -1); ++i)
    {
        cur = 0;
        for (j = 1; j <= nr; ++j)
            if ((i >> (j-1)) & 1)
                cur += 1 << (u[j]-1);
        contra = conf & (~cur);
        
        v2 = solve(k, contra);

        for (j = 1; j <= nr; ++j)
            if ((i >> (j-1)) & 1)
            {
                val = u[j];

                v1 = solve(val, cur);
                best = MIN(best, cost[k][val] + MAX(v1, v2));
            }
    }
    
    min[k][conf] = best;
    return min[k][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;
}