#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int NCONFIG = (1 << 12) - 1, INF = 2e9, NMAX = 12;

int n, lim, d[NMAX + 2][NCONFIG + 2], cost[NMAX + 2][NMAX + 2];
bool included[NCONFIG + 2][NCONFIG + 2];

bool testBit (int x, int bit) {
    return x & (1 << bit);
}

void init() {
    int i, j;

    for(i = 0; i < n; ++ i)
        for(j = 0; j < lim; ++ j)
            d[i][j] = INF;
}

int f (int node, int config) {
    if(d[node][config] != INF)
        return d[node][config];

    int son, sonConfig;

    for(son = 0; son < n; ++ son)
        if(son != node && testBit(config, son)) {
            for(sonConfig = 0; sonConfig < lim; ++ sonConfig)
                if(included[config][sonConfig] && !testBit(sonConfig, node) && testBit(sonConfig, son))
                    d[node][config] = min(d[node][config], cost[node][son] + max(f(son, sonConfig), f(node, config ^ sonConfig)));
        }

    return d[node][config];
}

int main() {
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    int tc, ans, i, j, bit;

    for(i = 0; i <= NCONFIG; ++ i)
        for(j = 0; j <= NCONFIG; ++ j) {
            included[i][j] = 1;
            for(bit = 0; bit < NMAX && included[i][j]; ++ bit)
                if(testBit(j, bit) && !testBit(i, bit))
                    included[i][j] = 0;
        }

    scanf("%d", &tc);
    while(tc) {
        -- tc;

        scanf("%d", &n);
        lim = 1 << n;
        init();
        for(i = 0; i < n; ++ i) {
            for(j = 0; j < n; ++ j) {
                scanf("%d", &cost[i][j]);
                d[i][1 << j] = cost[i][j];
            }
            d[i][0] = 0;
        }

        for(i = 0; i < n; ++ i)
            for(j = 0; j < lim; ++ j)
                if(testBit(j, i))
                    d[i][j] = f(i, j);

        ans = INF;
        for(i = 0; i < n; ++ i)
            ans = min(ans, d[i][lim - 1]);

        printf("%d\n", ans);
    }
    return 0;
}