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

using namespace std;

const int INF = 0x3f3f3f3f;

int T, N;
int A[12][12], D[12][1 << 12];

int getP(int T, int mask)
{
    if (D[T][mask] != INF) return D[T][mask];
    int& now = D[T][mask];

    if (!(mask & (mask - 1)))
    {
        for (int i = 0; i < N; ++i)
            if (mask & (1 << i))
            {
                now = A[T][i];
                break;
            }
        return now;
    }

    for (int i = 0; i < N; ++i)
        if (mask & (1 << i))
        {
            int base = A[T][i];
            int newmask = mask ^ (1 << i);

            now = min(now, base + getP(T, newmask));
            now = min(now, base + getP(i, newmask));

            for (int m1 = (newmask & (newmask - 1)); m1 != 0; m1 = (m1 - 1) & newmask)
            {
                int m2 = (newmask ^ m1);
                now = min(now, max(base + getP(T, m1), base + getP(i, m2)));
            }
        }

    return now;
}

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

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

        memset(D, 0x3f, sizeof(D));
        fout << getP(0, (((1 << N) - 1) ^ 1)) << '\n';
    }

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