#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 13
#define inf maxn*10000

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

int main() {
    FILE *f1=fopen("cast.in", "r"), *f2=fopen("cast.out", "w");
    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);
    while(T--) {
         fscanf(f1, "%d\n", &N);
         for(i=1; i<=N; i++) {
              for(j=1; j<=N; j++) {
                   fscanf(f1, "%d", &A[i][j]);
              }
         }

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

         for(i=1; i<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++) {
                   vstareinc[j] = 0;
                   if(viz[j]) {
                        stare = stare + p2[N-j];
                   }
                   if(viz[j] == 1) {
                        stareinc = stareinc + p2[N-j];
                        vstareinc[j] = 1;
                   }
                   if(viz[j] == 2) {
                        difstari = difstari + p2[N-j];
                   }
              }

              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]));
                             }
                        }
                   }
              }*/

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

              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]);
    }

    fclose(f1); fclose(f2);
    return 0;
}