#include <iostream>
#include <cstdio>
#include <cstring>
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 P1[maxn + 1], P2[maxn + 1], P0[maxn + 1];

inline int min(int a, int b) {
	if (a < b)	return a;
	return b;
}	

inline int max(int a, int b) {
	if (a > b)	return a;
	return b;
}

inline int swap(int &a, int &b) {
	int aux = a; a = b; b = aux;
}

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; 
			  P1[0] = 0; P2[0] = 0;

              for(j=1; j<=N; j++) {
                   viz[N-j+1] = p % 3;
                   if(viz[N-j+1]) q++;
				   if (viz[N - j + 1] == 1)
					   P1[++P1[0]] = N - j + 1;
				   if (viz[N - j + 1] == 2)
					   P2[++P2[0]] = N - j + 1;
                   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];
                   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;
              }

//			  fprintf(stderr, "%d\n", P1[0]);

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

         }

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

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