#include <fstream>
#define DN 13
#define INF 2000000000
using namespace std;
ifstream fi("cast.in");
ofstream fo("cast.out");
int T;
int n;
int C[DN][DN],D[(1<<DN)][DN];
int main()
{
    fi>>T;
    for(int t=1;t<=T;t++)
    {
        fi>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                fi>>C[i][j];
        for(int mask=0;mask<(1<<n);mask++)
            for(int i=0;i<n;i++)
                if(mask&(1<<i))
                {
                    int mask1=mask^(1<<i);
                    if(!mask1)
                    {
                        D[mask][i]=0;
                        continue;
                    }
                    D[mask][i]=INF;
                    for(int mask2=mask1;mask2;mask2=(mask2-1)&mask1)
                        for(int j=0;j<n;j++)
                            if(mask2&(1<<j))
                                D[mask][i]=min(D[mask][i],C[i][j]+max(D[mask^mask2][i],D[mask2][j]));
                }
        fo<<D[(1<<n)-1][0]<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}