#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;

int t,n;
int y[15],x1,x2,x,b[(1<<12)+5],dp[(1<<12)+5][12],a[12][12];
inline void bktr(int pas)
{
    for(int i=0;i<3;i++)
    {
        y[pas]=i;


        if(i==1)
            x1+=(1<<pas);

        if(i==2)
            x2+=(1<<pas);

        x=(x1|x2);

        if(b[x]) dp[x][b[x]-1]=0;
            else
        {
            for(int j=0;j<=pas;j++)
            {
                if((x1>>j)&1)
                {
                    for(int k=0;k<=pas;k++)
                    {
                        if((x2>>k)&1)
                        {
                            dp[x][j]=min(dp[x][j],max(dp[x1][j],dp[x2][k])+a[j][k]);
                            dp[x][k]=min(dp[x][k],max(dp[x1][j],dp[x2][k])+a[k][j]);
                        }
                    }
                }
            }
        }

        if(pas<n-1)
            bktr(pas+1);

        if(i==1)
            x1-=(1<<pas);
        if(i==2)
            x2-=(1<<pas);
    }
}
int main()
{
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);

    scanf("%d",&t);

    for(int i=0;i<=12;i++)
        b[1<<i]=i+1;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        int l=(1<<n)-1;


        x1=0;
        x2=0;
        for(int i=0;i<(1<<n);i++)
        {
            for(int j=0;j<n;j++)
                dp[i][j]=inf;

        }

        bktr(0);
        printf("%d\n",dp[(1<<n)-1][0]);
    }

    return 0;

}