#include <iostream>
#include <fstream>
using namespace std;
const int nmax=12;
int lg[(1<<nmax)+5],dp[(1<<nmax)+5][nmax+1];
int c[nmax+5][nmax+5];
int st[nmax+5];
int n,i,j,k,t,x,p,u,A,B;
int main()
{
    ifstream f("cast.in");
    ofstream g("cast.out");
    f>>t;
    for(i=0;i<12;i++)
        lg[(1<<i)]=i;
    for(int cnt=1;cnt<=t;cnt++)
    {
        f>>n;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
              f>>c[i][j];
        for(i=0;i<(1<<n);i++)
            for(j=0;j<n;j++)
             dp[i][j]=(1<<30)-1;
        for(i=1;i<(1<<n);i++)
        {
            x=i;u=0;
            if((!(i&(i-1))))
            {
                dp[i][lg[i]]=0;
                continue;
            }
            while(x!=0)
            {
                st[++u]=lg[((x^(x-1))&x)];
                x=(x&(x-1));
            }
            if(st[1]==0) p=1;
            else p=u;
            x=(1<<n);
            for(j=1;j<=p;j++)
                for(k=1;k<=u;k++)
            {
                x=i;A=st[j];B=st[k];
               if(A!=B)
                while(x!=0)
                {
                    dp[i][A]=min(dp[i][A],c[A][B]+max(dp[(i^x)][A],dp[x][B]));
                    x=((x-1)&i);
                }
            }
        }
        g<<dp[(1<<n)-1][0]<<'\n';
    }
    return 0;
}