#include <cstdio>
#include <algorithm>
#define INF 2000000000

using namespace std;

int dp[15][10000],a[15][15],n;

inline int Cnt(int x)
{
    int sol=0,i;
    for(i=x;i>0;i=(i&(i-1)),++sol);
    return sol;
}

inline int memo(int nod, int stare)
{
    if(dp[nod][stare]!=-1)
        return dp[nod][stare];
    int i,cnt,t,stare1,cntt;
    if(!((1<<(nod-1))&stare))
    {
        dp[nod][stare]=INF;
        return INF;
    }
    dp[nod][stare]=INF;
    cnt=Cnt(stare);
    for(t=1;t<(1<<cnt);++t)
    {
        stare1=0;
        for(i=0,cntt=0;i<n;++i)
            if((1<<i)&stare)
            {
                ++cntt;
                if(cntt && (t&(1<<(cntt-1)))) stare1|=(1<<i);
            }
        if((1<<(nod-1))&stare1) stare1-=(1<<(nod-1));
        for(i=1;i<=n;++i)
            if(((1<<(i-1))&stare1))
                dp[nod][stare]=min(dp[nod][stare],a[nod][i]+max(memo(i,stare1),memo(nod,stare-stare1)));
    }
    return dp[nod][stare];
}

int main()
{
    int T,i,j;
    freopen ("cast.in","r",stdin);
    freopen ("cast.out","w",stdout);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j) scanf("%d", &a[i][j]);
        for(i=1;i<=n;++i)
            for(j=0;j<(1<<n);++j) dp[i][j]=-1;
        for(i=1;i<=n;++i) dp[i][(1<<(i-1))]=0;
        printf("%d\n", memo(1,(1<<n)-1));
    }
    return 0;
}