#include <cstdio>
#include <cstdlib>
#include <string>
#define pow(x) (1u<<(x))
#define inf 1012345678

using namespace std;

unsigned n, cost[16][16];
unsigned best[12][1<<12];
char ok[12][1<<12];

unsigned calc(unsigned p, unsigned biti)
{
    if (ok[p][biti]) return best[p][biti];
    ok[p][biti]=1;
    if (!biti) return 0;
    unsigned sol = inf, nb=0, i, j, k;
    unsigned poz[16], loc[16];
    for (i=0; i<n; i++)
        if (pow(i) & biti) loc[i]=pow(nb), poz[nb++]=i;
    unsigned mask, inv;
    for (i=0; i<n; i++)     
        if ((biti & pow(i)) && cost[p][i]<sol){
           for (j=0; j<pow(nb); j++)
           if (!(loc[i]&j)){
               for (k=mask=0; k<nb; k++)
                   if (j & pow(k)) mask+=pow(poz[k]);
               inv = (biti & (~mask)) - pow(i);
               unsigned val = cost[p][i] + calc(p, mask);
               if (val>=sol) continue;
               val = max(val, cost[p][i]+calc(i, inv));
               if (val < sol) sol=val;
           }
        }
    best[p][biti]=sol;
    return best[p][biti];
}

void solve()
{
     unsigned i, j;
     scanf("%u", &n);
     for (i=0; i<n; i++)
         for (j=0; j<n; j++)
             scanf("%u", cost[i]+j);
     memset(ok, 0, sizeof(ok));
     for (i=0; i<n; i++)
         for (j=0; j<n; j++)
             if (i!=j) best[i][pow(j)]=cost[i][j], ok[i][pow(j)]=1;
     printf("%d\n", calc(0, pow(n)-2));
}

int main()
{
    int tst;
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    scanf("%d", &tst);
    while (tst--) solve();
    return 0;
}