#include<cstdio>
#include<algorithm>
#define MAXN 15
#define MAXEXP 5000
#define INF 1000000000
using namespace std;
int cost[MAXN][MAXN];
int dp[MAXEXP][MAXN];
int main(){
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);
    int tests,test,n,i,j,k,l,mask;
    scanf("%d",&tests);
    for(test=1;test<=tests;test++){
        scanf("%d",&n);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                scanf("%d",&cost[i][j]);
        for(i=1;i<(1<<n);i++)
            for(j=0;j<n;j++)
                if(i&(1<<j))
                    if(i==(1<<j))
                        dp[i][j]=0;
                    else{
                        dp[i][j]=INF;
                        mask=(i-(1<<j));
                        for(k=mask;k>0;k=(k-1)&mask)
                            for(l=0;l<n;l++)
                                if(k&(1<<l))
                                    dp[i][j]=min(dp[i][j],cost[j][l]+max(dp[i^k][j],dp[k][l]));
                    }
        printf("%d\n",dp[(1<<n)-1][0]);
    }
    return 0;
}