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

void init() {
    int i, j;

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

bool included (int i, int j) {
    for(int bit = 0; bit < n; ++ bit)
        if(testBit(j, bit) && !testBit(i, bit))
            return 0;
    return 1;
}

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

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

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

    for(i = 0; i < comp.size(); ++ i) {
        son = comp[i];
        for(subset = 0; subset < (1 << comp.size()); ++ subset) {
            sonConfig = 0;
            for(bit = 0; bit < comp.size(); ++ bit)
                if(testBit(subset, bit))
                    sonConfig = sonConfig | (1 << comp[bit]);
            if(!testBit(sonConfig, son))
                continue;

            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;

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

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