#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];
    for (i=0; i<n; i++)
        if (pow(i) & biti) poz[nb++]=i;
    unsigned mask, inv;
    for (i=0; i<n; i++)     
        if (biti & pow(i)){
           for (j=0; j<pow(nb); j++){
               for (k=mask=0; k<nb; k++)
                   if ((j & pow(k)) && poz[k]!=i) mask+=pow(poz[k]);
               inv = (biti & (~mask)) - pow(i);
//               printf("%d %d -> (%d %d) (%d %d)\n", p, biti, p, mask, i, inv);
               unsigned val = cost[p][i] + max(calc(p, mask), calc(i, inv));
//               printf("%d %d %d %d\n", val, j, pow(nb), mask);
               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;
}