#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;
        for(i=0;i<n;i++)
            dp[i][1<<i]=0;
        for(mask=1;mask<(1<<n);mask++)
            for(i=0;i<n;i++)
            {
                if(mask&(1<<i)); else continue;
                int conf=mask^(1<<i);
                for(mask2=conf;mask2;mask2=(mask2-1)&conf)
                    for(j=0;j<n;j++)
                    {
                        if(mask2&(1<<j)); else continue;
                        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;
}