#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define MAX_N 16    
#define MAX_P2 4096

int T;
int n, i, j, n3, p, q, nr, k;
int a[MAX_N], b[MAX_N];
int A[MAX_N][MAX_N];
int c[MAX_N][MAX_P2];

void cit() {
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			scanf("%d", &A[i][j]);

	n3 = 1;
	for (i = 1; i <= n; i++)
		n3 *= 3;
}

void solve() { 
	memset(c, 0, sizeof(c));

    for (i = 0; i < (1 << n); i++)
		for (j = 1; j <= n; j++)
			c[j][i] = 2147000000;
	for (i = 1; i <= n; i++)
		c[i][1 << (i - 1)] = 0;

	for (k = 1; k < n3; k++) {
		int aux = k;
    	
		p = q = nr = a[0] = b[0] = 0;
		while (aux) {
			if (aux % 3 == 1) {
				p += 1 << nr;
				a[++a[0]] = nr + 1;
			}
           	if (aux % 3 == 2) {
				q += 1 << nr;
				b[++b[0]] = nr + 1;
			}
			aux /= 3; nr++;
		}

		for (i = 1; i <= a[0]; i++)
			for (j = 1; j <= b[0]; j++)
				c[a[i]][p + q] = min(c[a[i]][p + q], A[a[i]][b[j]] + max(c[b[j]][q], c[a[i]][p]));
	}
}

int main() {

    freopen("cast.in", "r", stdin);
	freopen("cast.out", "w", stdout);

    scanf("%d", &T);

    while (T--) {
		cit();
		solve();
		printf("%d\n", c[1][(1 << n) - 1]);
	}

	return 0;
}