#include <fstream>
#include <queue>
#include <algorithm>
#define mod 100003
using namespace std;
ifstream fin("cast.in");
ofstream fout("cast.out");
int d[1<<12][12],c[13][13];
int n,t,i,j,b,k;

int main()
{
    fin>>t;
    for(;t--;)
    {
        fin>>n;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                fin>>c[i][j];
        for(k=1;k<(1<<n);k++)
            for(i=0;i<n;i++)
                if(k&(1<<i))
                {
                    if(k==(1<<i))
                    {
                        d[k][i]=0;
                        continue;
                    }
                    d[k][i]=1000000000;
                    for(b=k-(1<<i);b;b=(b-1)&(k-(1<<i)))
                        for(j=0;j<=n;j++)
                            if(b&(1<<j))
                                d[k][i]=min(d[k][i],c[i][j]+max(d[b][j],d[k^b][i]));
                }
        fout<<d[(1<<n)-1][0]<<"\n";
    }

    return 0;
}