#include<cstdio>
#define INF 2000000000
int t,n,i,j,k,x[20][20],d[20][100000];
FILE *f,*g;
int minim(int a,int b){
    if(a<b)
        return a;
    return b;
}
int maxim(int a,int b){
    if(a>b)
        return a;
    return b;
}
int dp(int a,int b){
    if(d[a][b]!=INF)
        return d[a][b];
    int r=INF;
    for(int i=0;i<n;i++){
        if( (b & (1<<i) ) && i!=a ){
            r=minim( r, x[a][i] + dp(a, b ^ (1<<i) ) );
            int c=( b ^ (1<<a) ^ (1<<i) );
            for(int q=c;q>0;q=c&(q-1)){
                r=minim( r, x[a][i] + maxim( dp( a, b^q^(1<<i) ) , dp( i, q^(1<<i) ) ) );
            }
        }
    }
    d[a][b]=r;
    return r;
}
int main(){
    f=fopen("cast.in","r");
    g=fopen("cast.out","w");
    fscanf(f,"%d",&t);
    while(t--){
        fscanf(f,"%d",&n);
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                fscanf(f,"%d",&x[i][j]);
            }
        }
        for(i=0;i<n;i++){
            for(j=0;j<(1<<n);j++){
                d[i][j]=INF;
            }
            d[i][1<<i]=0;
        }
        fprintf(g,"%d\n",dp(0, (1<<n)-1 ));
    }







    fclose(f);
    fclose(g);
    return 0;
}