#include <fstream>

#include <cstring>
using namespace std;

const int MAX_N = 15;
const int INF = 0x3f3f3f3f;

ifstream f("bcast.in");
ofstream g("bcast.out");

int T, N;
int D[MAX_N][(1 << MAX_N)], C[MAX_N][MAX_N];

void read() {
    f >> N;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            f >> C[i][j];
        }
    }
}

int compute(int x, int conf) {
    if(D[x][conf] != INF)
        return D[x][conf];

    int n = 0;
    int v[MAX_N];

    for(int i = 0; i < N; ++i) {
        if(i != x && (conf & (1 << i)))
            v[n++] = i;
    }

    for(int conf1 = 1; conf1 < (1 << n); ++conf1) {
        int conf2 = 0;
        for(int i = 0; i < n; ++i) {
            if(conf1 & (1 << i)) {
                conf2 ^= (1 << v[i]);
            }
        }

        int conf3 = conf ^ conf2;
        for(int i = 0; i < n; ++i) {
            if(conf1 & (1 << i)) {
                D[x][conf] = min(D[x][conf], C[x][v[i]] + max(compute(v[i], conf2), compute(x, conf3)));
            }
        }
    }

    return D[x][conf];
}

void solve() {
    memset(D, INF, sizeof(D));

    for(int i = 0; i < N; ++i)
        D[i][(1 << i)] = 0;

    D[0][(1 << N) - 1] = compute(0, (1 << N) - 1);
}

void write() {
    g << D[0][(1 << N) - 1] << "\n";
}

int main() {
    f >> T;
    for(int t = 1; t <= T; ++t) {
        read();
        solve();
        write();
    }

    f.close();
    g.close();

    return 0;
}