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

using namespace std;

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

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);
    pair<unsigned, unsigned> ord[12];
    for (i=k=0; i<n; i++)
        if (biti & pow(i)) ord[k++] = make_pair(cost[p][i], i);
    sort(ord, ord+nb+1);
    for (unsigned ind=0; ind<=nb; ind++)     
        if (ord[ind].first<sol){
           i = ord[ind].second;
           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;
               #define W(k) if (j & pow(k)) mask+=poz[k];
               W(0) W(1) W(2) W(3) W(4) W(5) W(6) W(7) W(8) W(9)
               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 sol;
}

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

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