#include<stdio.h>
#include<stdlib.h>
#include<algorithm>

const int maxn = 13;
const int maxn2 = (1 << 13);
const int inf = 60000;
int i;
int j;
int min(int i,int j){
        return i > j ? j : i;
}

bool ver[maxn][maxn2];
unsigned short din[maxn][maxn2];
int n;
int max(int i,int j)
{
        return i > j ? i : j;
}
int conf1;
unsigned short c[maxn][maxn];
int t;

int solve(int nod,int conf)
{
        if (ver[nod][conf]) return din[nod][conf];
        int i;
        int p;
        int j;
        int s[13];
        int nr = 0;
        ver[nod][conf] = 1;
        din[nod][conf] = inf;
        int conf1 = 0;
        memset(s,0,sizeof(s));
        for(p = 1,i = 1;p <= conf;p <<= 1, ++i)
        {
                if ((conf & p) != 0 && i != nod)
                {
                        s[nr] = i;
                        nr++;
                }
        }
        if (nr == 0)
        {
                din[nod][conf] = 0;
                return din[nod][conf];
        }
        for(j = 1;j < (1 << nr); ++j)
        {
               conf1 = 0;
               for(i = 0;i < nr;++i)
               {
                        if (j & (1 << i)) conf1 += 1 << (s[i] - 1);
               }
               for(i = 0;i < nr; ++i)
               {
                        if (((1 << (s[i] - 1)) & conf1) == 0) continue;
                        din[nod][conf] = min(din[nod][conf],c[nod][s[i]] + max(solve(nod,(conf & (~conf1))),solve(s[i],conf1)));
                }
        }

     //   printf("%d :  %d %d\n",din[nod][conf],nod,conf);
        return din[nod][conf];
}

int main()
{
        freopen("cast.in","r",stdin);
        freopen("cast.out","w",stdout);
        scanf("%d",&t);
        for(;t;t--)
        {
                scanf("%d",&n);
                memset(c,0,sizeof(c));
                for(i = 1;i <= n; ++i)
                {
                        for(j = 1;j <= n; ++j)
                        {
                                scanf("%hd",&c[i][j]);
                        }
                }
                memset(din,0,sizeof(din));
                memset(ver,0,sizeof(ver));

                for(i = 1;i <= n; ++i)
                {
                        ver[i][(1 << (i - 1))] = 1;
                        din[i][(1 << (i - 1))] = 0;
                }
                printf("%d\n",solve(1,(1 << n) - 1));
        }
        return 0;
}