#include <stdio.h>

#define maxN    20
#define maxM    10000
#define oo      (int) 1e9

int A[maxN][maxN], ind[maxN], C[maxM][maxN], N;

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

void baga_marfa (int mask) {
        int Size = 0, j, k, p, q, nowp, nowq;
                
	for (j = 0; j < N; ++ j)
		if (mask & (1 << j))
			ind[ ++ Size ] = j + 1;

	for (j = 1; j < (1 << Size) - 1; ++ j) {
		k = 0;
		for (p = 0; p < Size; ++ p)
			if ( (j & (1 << p) ) != 0)
			        k += 1 << (ind[p + 1] - 1);

		for (p = 1; p <= Size; ++ p)
                        if ( ( (1 << (ind[p] - 1) ) & k ) == 0 )
				for (q = 1; q <= Size; ++ q) {
				        nowp = ind[p];
				        nowq = ind[q];
					if (p != q && ( (1 << (nowq - 1) ) & k) != 0)
						C[mask][nowp] = min(C[mask][nowp], A[nowp][nowq] + max(C[k][nowq], C[mask - k][nowp])); 
			}
	}
}

void solve () {
        int i, j;
        // initializare :
        for (i = 0; i < (1 << N); ++ i)
                for (j = 1; j <= N; ++ j)
                        C[i][j] = oo;
        
        for (i = 1; i <= N; ++ i)       C[1 << (i - 1)][i] = 0;
        
        // pentru fiecare configuratie bag dinamica
        
        for (i = 0; i < (1 << N); ++ i) {
                baga_marfa (i);
        }
        
        printf("%d\n", C[(1 << N) - 1][1]);
}

int main () {
        int i, j, T;
        
        freopen("cast.in", "r", stdin);
        freopen("cast.out", "w", stdout);
        
        for (scanf("%d", &T); T -- ;) {
                scanf("%d", &N);
                
                for (i = 1; i <= N; ++ i)
                        for (j = 1; j <= N; ++ j)
                                scanf("%d", &A[i][j]);
                                
                solve ();
        }
        
        return 0;
}