#include <cstdio>
#include <cstring>

#define Nmax 13
#define INF 0x3f3f3f3f

int n;
int mat[Nmax][Nmax];
int d[Nmax][1 << Nmax];

inline int max(int a, int b)
{
	if (a > b) return a;
    else return b;
}

inline int min(int a, int b)
{
	if (a < b) return a;
    else return b;
}

int solve(int nod, int mask)
{
    if (d[nod][mask] < INF)
        return d[nod][mask];
    if (((1 << (nod - 1)) & mask) == 0)
    	return d[nod][mask];
    
    int i, j, ct = 0, mask1, mask2, mask3;
    int sir[Nmax];

    for (i = 1; i <= n; ++i)
    	if (i != nod && (1 << (i - 1)) & mask)
        	sir[++ct] = i;

    for (i = 1; i <= n; ++i)
    	if (i != nod && (1 << (i - 1)) & mask)
            for (mask1 = 1; mask1 < 1 << ct; ++mask1)
            {
            	mask2 = 0;
                for (j = 1; j <= ct; ++j)
                	if ((1 << (j - 1)) & mask1)
                        mask2 += 1 << (sir[j] - 1);
                mask3 = mask ^ mask2;
                
                d[nod][mask] = min(d[nod][mask], mat[nod][i] + max(solve(i, mask2), solve(nod, mask3)));
            }

	//printf("gata %d %d --> %d\n", nod, mask, d[nod][mask]);

	return d[nod][mask];
}

void write()
{
    int i, sol = INF;

    memset(d, 0x3f, sizeof(d));
    for (i = 1; i <= n; ++i)
    {
    	d[i][0] = 0;
        d[i][1 << (i - 1)] = 0;
    }
    for (i = 1; i <= n; ++i)
		if (solve(i, (1 << n) - 1) < sol)
        	sol = solve(i, (1 << n) - 1);
    printf("%d\n", sol);
}

void citire()
{
	int i, j, t;
    
	scanf("%d\n", &t);
    while (t > 0)
    {
    	scanf("%d\n", &n);
        for (i = 1; i <= n; ++i)
        	for (j = 1; j <= n; ++j)
            	scanf("%d", &mat[i][j]);
        write();
		--t;
    }
}

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