#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
#define maxn 13
#define inf 9999999

int T, N;
int p3[maxn], p2[maxn], viz[maxn], vstare[maxn], vstareinc[maxn], vdifstari[maxn];
int Tmin[maxn][1 << maxn];
int A[maxn][maxn];

int main() {
    //FILE *f1=fopen("cast.in", "r"), *f2=fopen("cast.out", "w");
    fstream f1, f2;
    f1.open("cast.in", ios::in);
    f2.open("cast.out", ios::out);
    int i, j, p, q;

    p3[0] = 1; p2[0] = 1;
    for(i=1; i<maxn; i++) {
         p3[i] = p3[i-1] * 3;
         p2[i] = p2[i-1] * 2;
    }

    //fscanf(f1, "%d\n", &T);
    f1>>T;
    while(T--) {
         //fscanf(f1, "%d\n", &N);
         f1>>N;
         for(i=1; i<=N; i++) {
              for(j=1; j<=N; j++) {
                   //fscanf(f1, "%d", &A[i][j]);
                   f1>>A[i][j];
              }
         }

         for(i=0; i<=(1 << N); i++) {
              for(j=1; j<=N; j++) {
                   Tmin[j][i] = inf;
              }
         }

         for(i=1; i<2*p3[N]; i++) {
              p = i; q = 0;
              for(j=1; j<=N; j++) {
                   viz[N-j+1] = p % 3;
                   if(viz[N-j+1]) q++;
                   p = p / 3;
              }

              int stare = 0, stareinc = 0, difstari = 0;
              for(j=1; j<=N; j++) {
                   vstare[j] = vstareinc[j] = vdifstari[j] = 0;
                   if(viz[j]) {
                        stare = stare + p2[N-j];
                        vstare[j] = 1;
                   }
                   if(viz[j] == 1) {
                        stareinc = stareinc + p2[N-j];
                        vstareinc[j] = 1;
                   }
                   if(viz[j] == 2) {
                        difstari = difstari + p2[N-j];
                        vdifstari[j] = 1;
                   }
              }

              if(q == 1) {
                   //in caz ca submultimea are un singur element
                   for(j=1; j<=N; j++) {
                        if(viz[j]) {
                             Tmin[j][stare] = 0;
                             break;
                        }
                   }
                   continue;
              }

              for(j=1; j<=N; j++) {
                   if(viz[j]) {
                        //calculez Tmin[j][stare]
                        //iterez dupa un nod din stareinc
                        for(p=1; p<=N; p++) {
                             if(vstareinc[p]) {
                                  Tmin[j][stare] = min(Tmin[j][stare], A[j][p] + max(Tmin[p][stareinc], Tmin[j][difstari]));
                             }
                        }
                   }
              }
         }

         //fprintf(f2, "%d\n", Tmin[1][(1 << N) - 1]);
         f2<<Tmin[1][(1 << N) - 1]<<'\n';
    }

    //fclose(f1); fclose(f2);
    f1.close(); f2.close();
    return 0;
}