#include<stdio.h>
#define Nm 12
#define Inf 1000000
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int M[Nm][1<<Nm],C[Nm][Nm],P[Nm],A[Nm],n,s,m,p,x,a,v;

void read()
{
    int i,j;

    scanf("%d",&n);
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            scanf("%d",&C[i][j]);
}

void back(int k)
{
    int i;
    
    if(k==x)
        for(i=0;i<x;++i)
        {
            v=C[s][P[A[i]]]+max(M[s][m^a],M[P[A[i]]][a^1<<P[A[i]]]);
            M[s][m]=min(M[s][m],v);
        }
    else
        for(i=A[k-1]+1;i<=p-x+k;++i)
        {
            A[k]=i; a|=1<<P[i];
            back(k+1);
            a^=1<<P[i];
        }
}

void solve()
{
    int i;

    for(m=1;m<1<<n;++m)
        for(s=0;s<n;++s)
        {
            if(m&1<<s)
                continue;
            M[s][m]=Inf;
            for(p=i=0;i<n;++i)
                if(m&1<<i)
                    P[p++]=i;
            for(x=1;x<=p;++x)
                for(i=0;i<p;++i)
                {
                    A[0]=i; a=1<<P[i];
                    back(1);
                }
        }
}

int main()
{
    int t;

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

    scanf("%d",&t);
    while(t--)
    {
        read();
        solve();
        printf("%d\n",M[0][(1<<n)-2]);
    }
    return 0;
}