#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], sir1[maxn], sir2[maxn];

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

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;
                   p = p / 3;
              }

              int stare = 0, stareinc = 0, difstari = 0;
              for(j=1; j<=N; j++) {
                   if(viz[N-j+1]) {
					   q++;
					   stare += p2[N - j];
					   if (viz[N - j + 1] == 1) {
						   P1[++P1[0]] = N - j + 1;
						   stareinc += p2[N - j];
					   }
					   else
						   if (viz[N - j + 1] == 2) {
							   P2[++P2[0]] = N - j + 1;			   
							   difstari += p2[N - j];
						   }
				   }
              }

              if(q == 1) {
                   for(j=1; j<=N; j++) {
                        if(viz[j]) {
                             Tmin[j][stare] = 0;
                             break;
                        }
                   }
                   continue;
              }

			for (j = 0; j <= N; j++) {
				sir1[j] = Tmin[j][stareinc];
				sir2[j] = Tmin[j][difstari];
			}

              for(j=1; j<=N; j++) {
                   if(viz[j]) {
					   int scula = max(P1[0], P2[0]);
                        for(p=1; p<=scula; p++)  {
                        	if (p <= P1[0]) Tmin[j][stare] = min(Tmin[j][stare], A[j][P1[p]] + max(sir1[P1[p]], sir2[j]));
//                        	if (p <= P2[0]) Tmin[j][stare] = min(Tmin[j][stare], A[j][P2[p]] + max(sir2[P2[p]], sir1[j]));
						}
                    }
              }

         }

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

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