#include<fstream>
using namespace std;
ifstream fi("cast.in");
ofstream fo("cast.out");
int T,t,n,i,j,k,val,m,Dp[15][4100],D[15][15];
int main()
{
    fi>>T;
    for(t=1; t<=T; t++)
    {
        fi>>n;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                fi>>D[i][j];
        for(i=1; i<=n; i++)
            for(j=0; j<(1<<n); j++)
                Dp[i][j]=1000000000;
        for(j=0; j<(1<<n); j++)
        {
            for(i=1; i<=n; i++)
            {
                if((1<<(i-1))&j)
                {
                    m=j^(1<<(i-1));
                    if(m==0)
                    {
                        Dp[i][j]=0;
                        continue;
                    }
                    for(val=m; val>=0; val--)
                    {
                        if(((val^m)&m)==(val^m))
                        {
                            for(k=1; k<=12; k++)
                            {
                                if((1<<(k-1))&m)
                                    Dp[i][j]=min(Dp[i][j],D[i][k]+max(Dp[i][j^val],Dp[k][val]));
                            }
                        }
                    }
                }
            }
        }
        fo<<Dp[1][(1<<n)-1]<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}