#include <cstdio>
#include <queue>
using namespace std;
int a[20][20],p2[5000];
int d[5000][15];
int unu,doi,all,n;
void back (int pas){
    int i,x,y;
    if (pas==n)
        return;
    for (i=0;i<3;i++){
        if (i==1)
            unu=unu+(1<<pas); /// conf-conf1
        if (i==2)
            doi=doi+(1<<pas); /// conf1
        if (i)
            all=all+(1<<pas); /// conf
        if (p2[all]){ /// d[2^k][k]=0
            //printf ("%d ",all);
            d[all][p2[all]-1]=0;
        }
        else {
            for (x=0;x<=pas;x++){
                if (unu&(1<<x)){ /// x e doar in conf
                    for (y=0;y<=pas;y++){
                        if (doi&(1<<y)){ /// y e doar in conf1
                            d[all][x]=min(d[all][x],max(d[doi][y],d[unu][x])+a[x][y]);
                            d[all][y]=min(d[all][y],max(d[unu][x],d[doi][y])+a[y][x]);
                        }
                    }
                }
            }
        }
        back(pas+1);
        if (i==1)
            unu=unu-(1<<pas); /// conf-conf1
        if (i==2)
            doi=doi-(1<<pas); /// conf1
        if (i)
            all=all-(1<<pas); /// conf
    }
}
int main()
{
    FILE *fin=fopen ("cast.in","r");
    FILE *fout=fopen ("cast.out","w");
    int t,i,j;
    fscanf (fin,"%d",&t);
    for (;t;t--){
        fscanf (fin,"%d",&n);
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                fscanf (fin,"%d",&a[i][j]);
        for (i=0;i<(1<<n);i++){
            for (j=0;j<n;j++)
                d[i][j]=1000000000; /// radacina j, nodurile din i apar
        }
        for (i=0;i<n;i++)
            p2[(1<<i)]=i+1;
        back (0);
        fprintf (fout,"%d\n",d[(1<<n)-1][0]);
    }
    return 0;
}