#include <iostream>
#include <fstream>
using namespace std;
const int nmax=55000;
int trans[nmax],best[nmax],b[nmax],viz[nmax];
int c[15][15],p3[15];
int n,i,j,t;
int memo(int A,int B,int curr)
{
     if(viz[curr]) return trans[curr];
     viz[curr]=1;
     if(B==0) return 0;
     for(int ind=0;ind<n;ind++)
        for(int idx=0;idx<n;idx++)
          if(((1<<ind)&A)&&((1<<idx)&B))
     {
         if(c[ind][idx]<trans[curr])
         {
              trans[curr]=min(trans[curr],max(c[ind][idx],memo(A-(1<<ind),B-(1<<idx),curr-p3[ind]-2*p3[idx])));
         }
     }
     return trans[curr];
}
int decod(int A,int B)
{
    int ret=0;
    for(int idx=0;idx<n;idx++)
    {
        if(((1<<idx)&A)) ret+=p3[idx];
        if(((1<<idx)&B)) ret+=p3[idx];
    }
    return ret;
}
int main()
{
    ifstream f("cast.in");
    ofstream g("cast.out");
    f>>t;
    p3[0]=1;
    for(i=1;i<=12;i++)
        p3[i]=3*p3[i-1];
    for(i=1;i<(1<<12);i++)
        b[i]=b[(i&(i-1))]+1;
    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++)
            best[i]=(1<<30);
        best[1]=0;
        for(i=1;i<p3[n];i++)
            trans[i]=(1<<30)-1,viz[i]=0;
        for(i=0;i<(1<<n);i++)
        {
            j=i;
            while(j!=0)
            {
                if(b[(i^j)]>=b[j])
                    best[i]=min(best[i],best[(i^j)]+memo((i^j),j,decod(i,j)));
                j=((j-1)&i);
            }
        }
        g<<best[(1<<n)-1]<<'\n';
    }
    return 0;
}