#include <fstream>

#include <cstring>
using namespace std;

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

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

int T, N;
int D[MAX_N][(1 << MAX_N)], dp[(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];
        }
    }
}

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

    D[0][1] = 0;
    dp[1] = 0;

    int v[MAX_N];

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

        for(int i = 0; i < N; ++i) {
            if((conf & (1 << i)) == 0) {
                continue;
            }

            for(int j = 0; j < k; ++j) {
                if(v[j] == i) {
                    swap(v[j], v[k - 1]);
                    j = k;
                }
            }

            for(int j = 0; j < k - 1; ++j) {
                for(int conf1 = 1; conf1 < (1 << (k - 1)); ++conf1) {
                    if((conf1 & (1 << j)) == 0) {
                        continue;
                    }

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

                    D[i][conf] = min(D[i][conf], C[v[j]][i] + max(D[v[j]][conf2], dp[conf ^ (1 << i)]));
                }
            }

            dp[conf] = min(dp[conf], D[i][conf]);
        }
    }
}

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

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

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

    return 0;
}