#include<stdio.h>
 
#define maxn 15
#define INF (1<<29)
 
FILE*f=fopen("cast.in","r");
FILE*g=fopen("cast.out","w");
 
int n;
int C[maxn][maxn],D[maxn][1<<12];
 
inline int min ( const int &a , const int &b ){
    return a <= b ? a : b;
}
 
inline int max ( const int &a , const int &b ){
    return a >= b ? a : b;
}
 
int solve ( int nod , int conf ){
    if ( D[nod][conf] != INF )  return D[nod][conf];
     
    int nr = 0; int c[maxn],pozi;
    for ( int i = 0 ; i < n ; ++i ){
        if ( conf & (1<<i) ){
            c[nr++] = i;
            if ( i == nod )
                pozi = nr-1;
        }
    }
     
    if ( nr == 1 ){
        D[nod][conf] = 0;
        return 0;
    }
     
    for ( int i = 0 ; i < nr ; ++i ){
        if ( c[i] != nod ){
            D[nod][conf] = min(D[nod][conf],solve(c[i],conf^(1<<nod)) + C[nod][c[i]]);
        }
    }
     
    for ( int i = 1 ; i < (1<<nr) ; ++i ){
        if ( i & (1<<pozi) )  continue ;
         
        int new_conf = conf;
        for ( int j = 0 ; j < nr ; ++j ){
            if ( i & (1<<j) )
                new_conf ^= (1<<c[j]);
        }
         
        for ( int j = 0 ; j < nr ; ++j ){
            if ( i & (1<<j) ){
                int now = max(solve(c[j],conf ^ new_conf),solve(nod,new_conf)) + C[nod][c[j]];
                D[nod][conf] = min(D[nod][conf],now);
            }
        }
    }
     
    return D[nod][conf];
}
 
int main () {
     
    int t;
    fscanf(f,"%d",&t);
     
    for ( int ii = 1 ; ii <= t ; ++ii ){
         
        fscanf(f,"%d",&n);
        for ( int i = 0 ; i < n ; ++i ){
            for ( int j = 0 ; j < n ; ++j ){
                fscanf(f,"%d",&C[i][j]);
            }
        }
         
        for ( int i = 0 ; i < n ; ++i ){
            for ( int j = 0 ; j < (1<<n) ; ++j ){
                D[i][j] = INF;
            }
        }
         
        fprintf(g,"%d\n",solve(0,(1<<n)-1));
    }
     
    fclose(f);
    fclose(g);
     
    return 0;
}