#include <fstream>
#include <vector>
#define NMax 13
#define INF 2000000000

using namespace std;

int n, G[NMax][NMax], dp[NMax][(1<<NMax)];

inline int Solve(const int rad, const int conf)
{
    if (dp[rad][conf] != INF)
        return dp[rad][conf];
    int v[NMax], nv, i, j;
    nv = 0;
    for (i = 0; i<n; ++i)
        if (rad != i && conf&(1<<i))
            v[nv++] = i;
    for (i = 0; i<(1<<nv); ++i)
    {
        int confsubtree = 0, subtree;
        for (j = 0; j < nv; ++j)
            if (i & (1<<j))
                confsubtree += (1<<v[j]);
        for (subtree = 0; subtree < nv; ++subtree)
            if (confsubtree & (1<<v[subtree]))
                dp[rad][conf] = min(dp[rad][conf], G[rad][v[subtree]] + max(Solve(rad, conf - confsubtree), Solve(v[subtree], confsubtree)));
    }
    return dp[rad][conf];
}

int main()
{
    ifstream f ("cast.in");
    ofstream g ("cast.out");
    int nrt, i, j; f>>nrt;
    while(nrt--)
    {
        f>>n;
        for (i = 0; i<n; ++i)
        {
            for (j = 0; j<n; ++j)
                f>>G[i][j];
            for (j = 0; j<(1<<n); ++j)
                dp[i][j] = INF;
            dp[i][(1<<i)] = 0;
        }
        g<<Solve(0, (1<<n) - 1)<<"\n";
    }
    f.close();
    g.close();
    return 0;
}