#include <cstdio>
#include <cstring>

using namespace std;

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

int n, t;
int mat[Nmax][Nmax],sir[Nmax];
int d[Nmax][1<<Nmax];

void solve()
{
    int i,j,m,m1,m2,m3,ct,nod,lim;
    
    memset(d, 0x3f, sizeof(d));
    for (i=1; i<=n; ++i)
    	d[i][0]=0;
	for (m=1; m<1<<n; ++m)
        for (nod=1; nod<=n; ++nod)
            if ((m>>(nod-1))&1)
            {
            	if ((m^(1<<(nod-1)))==0)
                {
                	d[nod][m] = 0;
                    continue;
            	}
            	ct=0;
                for (i=0; i<n; ++i)
                	if (nod!=i+1 && ((m>>i)&1))
                        sir[++ct]=i+1;
                for (m1=1; m1<1<<ct; ++m1)
                {
                    m2=0;
                    for (i=1; i<=ct; ++i)
                    	if ((m1>>(i-1))&1)
                        	m2+=1<<(sir[i]-1);
                    m3=m^m2;
                    for (i=1; i<=ct; ++i)
                        d[nod][m]=min(d[nod][m],mat[nod][sir[i]]+max(d[sir[i]][m2],d[nod][m3]));
                }
            }
    printf("%d\n",d[1][(1<<n)-1]);
}

void citire()

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

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