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

using namespace std;

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

inline int memo(int nod, int stare)
{
    if(dp[nod][stare]!=-1)
        return dp[nod][stare];
    int i,cnt,t,stare1,cntt,x;
    if(!((1<<(nod-1))&stare))
    {
        dp[nod][stare]=INF;
        return INF;
    }
    dp[nod][stare]=INF;
    x=stare^(1<<(nod-1));
    for(stare1=x;stare1>0;stare1=((stare1-1)&x))
    {
        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;
}