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

int T, N;
int p3[maxn], p2[maxn], viz[1 << maxn][maxn], vizst[maxn], stnew[maxn], vstareinc[maxn], vdifstari[maxn];
int Tmin[maxn][1 << maxn];
int A[maxn][maxn];
bool stareviz[1 << maxn];

void solve(int stare) {
    if(stareviz[stare]) {
         return;
    }

    stareviz[stare] = 1;

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

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

    for(i=1; i<(1 << q); i++) {
         p = i;
         for(j=1; j<=N; j++) {
              stnew[j] = 0;
              if(viz[stare][j]) {
                   if(p % 2) {
                        stnew[j] = 2;
                   }
                   else {
                        stnew[j] = 1;
                   }

                   p = p / 2;
              }
         }

         int stareinc = 0, difstari = 0;
         for(j=1; j<=N; j++) {
              vstareinc[N - j + 1] = vdifstari[N - j + 1] = 0;

              if(stnew[N - j + 1] == 1) {
                   stareinc = stareinc + p2[j-1];
                   vstareinc[N - j + 1] = 1;
              }
              if(stnew[N - j + 1] == 2) {
                   difstari = difstari + p2[j-1];
                   vdifstari[N - j + 1] = 1;
              }
         }

         solve(stareinc);
         solve(difstari);

         for(j=1; j<=N; j++) {
              if(stnew[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]));
                        }
                        if(vdifstari[p]) {
                             Tmin[j][stare] = min(Tmin[j][stare], A[j][p] + max(Tmin[p][difstari], Tmin[j][stareinc]));
                        }
                  }
              }
         }
    }
}

int main() {
    FILE *f1=fopen("cast.in", "r"), *f2=fopen("cast.out", "w");
    int i, j;

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

         memset(stareviz, 0, sizeof(stareviz));

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

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