#include<stdio.h>
#include<string.h>
#include<vector>
#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 testBit (int x, int bit) {
    return x & (1 << bit);
}

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

    int i, sonConfig, subset;
    vector <int> comp;

    for(i = 0; i < n; ++ i)
        if(i != node && testBit(config, i))
            comp.push_back(i);

    d[node][config] = INF;
    for(subset = 0; subset < (1 << comp.size()); ++ subset) {
        sonConfig = 0;
        for(i = 0; i < comp.size(); ++ i)
            if(testBit(subset, i))
                sonConfig = sonConfig | (1 << comp[i]);

        for(i = 0; i < comp.size(); ++ i)
            if(testBit(sonConfig, comp[i]))
                d[node][config] = min(d[node][config], cost[node][comp[i]] + max(f(comp[i], 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;

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

        scanf("%d", &n);
        lim = 1 << n;
        memset(d, -1, sizeof(d));
        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);

        printf("%d\n", f(0, lim - 1));
    }
    return 0;
}