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

int T, N, stare, stareinc, difstari;
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], sir3[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;
              }
         }

		 viz[1] = 1;
		 stare = stareinc = p2[N - 1];
		 difstari = 0;

         for(i=1; i<p3[N]; i++) {
              p = i; q = 0; 
			  P1[0] = 0; P2[0] = 0;

			  j = 1;
			  while (viz[j] == 2) {
				  viz[j] = 0;
				  stare -= p2[N - j];
				  difstari -= p2[N - j];
				  j++;
			  }

			  if (viz[j] == 0) {
				stare += p2[N - j];
				stareinc += p2[N - j];
			  }
			  else {
				difstari += p2[N - j];
				stareinc -= p2[N - j];
			  }
			  viz[j]++;

              for(j=1; j<=N; j++) {
                   if(viz[N-j+1]) {
					   q++;
					   if (viz[N - j + 1] == 1) 
						   P1[++P1[0]] = N - j + 1;
					   
					   else
						   if (viz[N - j + 1] == 2) 
							   P2[++P2[0]] = N - j + 1;			   
						   
				   }
              }

              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];
				sir3[j] = max(sir1[j], sir2[j]);
			}
				
			int bula = 1000000000;
              for(j=1; j<=N; j++) {
                   if(viz[j]) {
					   int scula = max(P1[0], P2[0]);
                        for(p=1; p<=scula; p++)  {
                        	 bula = min(A[j][P2[p]] + max(sir2[P2[p]], sir1[j]), A[j][P1[p]] + max(sir1[P1[p]], sir2[j])); //le unesc
                        	 Tmin[j][stare] = min(Tmin[j][stare], bula); ;
						}
                    }
              }

         }

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

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