#include <algorithm>
#include <fstream>
#include <cstring>

using namespace std;

const int Nmax = 12;

int Cost[Nmax][Nmax], Dp[Nmax][1 << Nmax];
int N;

int getAns(int node, int conf) {
    if (Dp[node][conf] != -1) return Dp[node][conf];
    int& ans = Dp[node][conf];
    if (conf == (1 << node)) ans = 0;
    else {
        ans = 0x3f3f3f3f;
        for (int next = 0; next < N; ++next) {
            if (next == node || (conf & (1 << next)) == 0) continue;
            ans = min(ans, Cost[node][next] + getAns(node, conf ^ (1 << next)));
            int x = conf ^ (1 << next) ^ (1 << node);
            for (int nconf = x; nconf > 0; nconf = (nconf - 1) & x)
                ans = min(ans, max(getAns(next, nconf ^ (1 << next)), getAns(node, conf ^ nconf ^ (1 << next))) + Cost[node][next]);
        }
    }
    return ans;
}

int main()
{
    ifstream fin("cast.in");
    ofstream fout("cast.out");

    int T;
    fin >> T;

    while (T--) {
        fin >> N;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                fin >> Cost[i][j];

        memset(Dp, -1, sizeof Dp);
        fout << getAns(0, (1 << N) - 1) << '\n';
    }

    fin.close();
    fout.close();
}