#include <cstdio>
#define INF 100000000
#define MAXN 12
int d[1<<MAXN][MAXN], m[MAXN][MAXN], v[MAXN];
inline int max2(int a, int b){
    if(a>b) return a;
    else return b;
}
inline int min2(int a, int b){
    if(a<b) return a;
    else return b;
}
int main(){
    int t, n, i, j, k, p, q, mask, c;
    FILE *fin, *fout;
    fin=fopen("cast.in", "r");
    fout=fopen("cast.out", "w");
    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", &m[i][j]);
            }
        }
        for(i=1; i<(1<<n); i++){
            k=0;
            for(j=0; j<n; j++){
                if(i&(1<<j)) v[k++]=j;
            }
            if(k==1) d[i][v[0]]=0;
            else{
                for(j=0; j<k; j++){
                    d[i][v[j]]=INF;
                    c=((1<<k)-1)^(1<<j);
                    for(p=c; p>0; p=((p-1)&c)){
                        mask=0;
                        for(q=0; q<k; q++){
                            if(p&(1<<q)){
                                mask^=1<<v[q];
                            }
                        }
                        for(q=0; q<k; q++){
                            if((v[j]!=v[q])&&(p&(1<<q))){
                                d[i][v[j]]=min2(d[i][v[j]], m[v[j]][v[q]]+max2(d[i^mask][v[j]], d[mask][v[q]]));
                            }
                        }
                    }
                }
            }
        }
        fprintf(fout, "%d\n", d[(1<<n)-1][0]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}