#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 12, inf = (1ll << 31) - 1;
int a [N + 2][N + 2], configfinal, n;
int dp [N + 2][(1 << N) + 2];

void read () {
    int i, j;

    scanf ("%d", &n);
    configfinal = (1 << n) - 1;
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
            scanf ("%d", &a [i][j]);
}

int solve (int x, int config) {
    int newconfig, i, cost, cost1, cost2, k, k1;

    if (dp [x][config] != inf)
        return dp [x][config];

    for (i = 0; i < n; i ++)
        if (((1 << i) & config) && i != x) {
            dp [x][config] = min (dp [x][config], a [x][i] + solve (x, config ^ (1 << i)));
            newconfig = config ^ (1 << x);
            newconfig = newconfig ^ (1 << i);
            for (k = newconfig; k; k = (k - 1) & newconfig) {
                k1 = k | (1 << i);
                cost1 = solve (i, k1);
                cost2 = solve (x, config - k1);
                cost = max (cost1, cost2);
                dp [x][config] = min (dp [x][config], a [x][i] + cost);
            }
        }
    return dp [x][config];
}

void init () {
    int i, lim, j;

    lim = (1 << n) - 1;
    for (i = 0; i < n; i ++) {
        for (j = 0; j <= lim; j ++)
            dp [i][j] = inf;
        dp [i][1 << i] = 0;
    }
}


int main () {
    int t, T;

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

    scanf ("%d", &T);
    for (t = 1; t <= T; t ++) {
        read ();
        init ();
        printf ("%d\n", solve (0, configfinal));
    }
    return 0;
}