#include <cstdio>
#include <algorithm>

using namespace std;

int t, n;
int cost[13][13];
int D[1<<12][12];

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

    scanf("%d", &t);

    while(t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &cost[i][j]);
            }
            for (int j = 0; j < (1<<n); j++) {
                D[j][i] = 0x3f3f3f3f;
            }
        }

        for (int i = 0; i < n; i++) {
            D[(1<<i)][i] = 0;
        }

        for (int m = 1; m < (1<<n); m++) {
            for (int i = 0; i < n; i++) {
                if (!(m & (1<<i)))
                    continue;
                for (int m1 = m - (1<<i); m1; m1 = (m - (1<<i)) & (m1 - 1)) {
                    for (int j = 0; j < n; j++) {
                        if (!(m1 & (1<<j)))
                            continue;
                        D[m][i] = min(D[m][i], cost[i][j] + max(D[m ^ m1][i], D[m1][j]));
                    }
                }
            }
        }

        printf("%d\n", D[(1<<n)-1][0]);
    }
    return 0;
}