#include <bits/stdc++.h>
#define maxN 12
#define INF (1<<30)
using namespace std;
int T,n,i,j,mask,conf,mask2,k;
int a[maxN][maxN];
int dp[maxN][(1<<12)];
int main()
{
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
        for(i=0;i<n;i++)
        {
            for(j=0;j<(1<<n);j++)
                dp[i][j]=INF;
            dp[i][1<<i]=0;
        }
        for(mask=1;mask<(1<<n);mask++)
            for(i=0;i<n;i++)
            if(mask&(1<<i))
                {
                    int conf=mask|(1<<i);
                    for(mask2=conf;mask2;mask2=(mask2-1)&conf)
                        for(j=0;j<n;j++)
                            if(mask2&(1<<j))
                                dp[i][mask]=min(dp[i][mask],a[i][j]+max(dp[i][mask^mask2],dp[j][mask2]));
                }
            printf("%d\n",dp[0][(1<<n)-1]);
    }
    return 0;
}