#include<cstdio>
#include<algorithm>

using namespace std;

int T, N, d[12][12], dp[12][4100];

int main ()
{
freopen ("cast.in", "r", stdin);
freopen ("cast.out", "w", stdout);

scanf ("%d", &T);
while (T --)
{
    scanf ("%d", &N);
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            scanf ("%d", &d[i][j]);
    for (int j=0; j < (1 << N); j++)
        for (int i=0; i<N; i++)
        if (j & (1 << i))
        {
            int msk1 = j ^ (1 << i);
            dp[i][j] = 1 << 26;
            if (!msk1) dp[i][j] = 0;
            for (int k=msk1; ;k = (k - 1) & msk1)
            {
                int msk2 = msk1 ^ k;
                for (int p=0; p<N; p++)
                    if (msk2 & (1 << p))
                        dp[i][j] = min (dp[i][j], d[i][p] + max (dp[i][j ^ msk2], dp[p][msk2]));
                if (k == 0) break;
            }
        }
    printf ("%d\n", dp[0][(1 << N) - 1]);
}

return 0;
}