#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[12], mask, inv, tot;
    for (i=0; i<n; i++)
        if (pow(i) & biti) nb++;
    nb--;
    tot = pow(nb);
    for (i=0; i<n; i++)     
        if ((biti & pow(i)) && cost[p][i]<sol){
           for (j=k=0; j<n; j++)
               if ((pow(j) & biti) && j!=i) poz[k++]=pow(j);
           for (j=0; j<tot; j++){
               mask=0;
               unsigned m1=0, m2=0;
               #define W(k) if (j & pow(k)) m1+=poz[k];
               #define Q(k) if (j & pow(k)) m2+=poz[k];
               W(0) Q(1) W(2) Q(3) W(4) Q(5) W(6) Q(7) W(8) Q(9);
               mask=m1+m2;
//               for (k=mask=0; k<nb; k++)
//                   if (j & pow(k)) mask+=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;
}