#include <cstdio>
#include <cstring>

#define Nmax 13
#define INF 0x3f3f3f3f
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))

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

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

	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;

        for (i = 1; i <= ct; ++i)
        {
        	v1 = solve(mask2, sir[i]);
	        v2 = solve(mask3, nod);
	        d[mask][nod] = min(d[mask][nod], mat[nod][sir[i]] + max(v1,v2));
        }
    }

    return d[mask][nod];
}

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]);

        memset(d, 0x3f, sizeof(d));
    	for (i = 1; i <= n; ++i)
	    {
    		d[0][i] = 0;
        	d[1 << (i - 1)][i] = 0;
	    }

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

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