#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;
            for (int nconf = 0; nconf < (1 << N); ++nconf) {
                if ((conf & nconf) != nconf || (nconf & (1 << next)) == 0 || (nconf & (1 << node)) != 0) continue;
                ans = min(ans, max(getAns(next, nconf), Cost[node][next] + getAns(node, conf ^ nconf)));
            }
        }
    }
    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();
}