/*
tMin[i][j]=costul minim pentru a conecta nodurile de la indicii din desc binara a lui j avand rad in i
*/
//#include <stdio.h>
#include<fstream>
#include<cstring>
#include<algorithm>
//#define MAX(a, b) ((a) > (b) ? (a) : (b))
//#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define Nmax 13
#define INF (1 << 30)
using namespace std;
ifstream f("cast.in"); ofstream g("cast.out");
int N,T,tComp[Nmax][Nmax],tMin[Nmax][(1<<Nmax)];
char v[Nmax][(1<<Nmax)];
int solve(int k, int conf)
{   if(v[k][conf]) return tMin[k][conf];
    v[k][conf]=1;
    int contra,i,j,u[Nmax],nr=0,cur,val,best=INF,v1,v2;
    for(i=1;i<=N;++i)
        if(i!=k)
            if((conf>>(i-1))&1) u[++nr]=i;
    if(nr==0) return 0;
    for(i=1;i<=((1<<nr)-1);++i)
    {   cur=0;
        for(j=1;j<=nr;++j)
            if ((i>>(j-1))&1)
                cur+=(1<<(u[j]-1));
        contra=conf&(~cur);
        v2=solve(k, contra);
        for(j=1;j<=nr;++j)
            if ((i>>(j-1))&1)
            {   val=u[j];
                v1=solve(val,cur); //
                best=min(best,tComp[k][val]+max(v1,v2)); //max(v1,v2)-ne asiguram ca parcurgem amandoi arborii
            }
    }
    tMin[k][conf]=best;
    return tMin[k][conf];
}
int main()
{   int i,j;
    f>>T;
    while(T--)
    {   memset(v,0,sizeof(v));
        f>>N;
        for(i=1;i<=N;++i)
            for(j=1;j<=N;++j)
                f>>tComp[i][j];
        g<<solve(1,(1<<N)-1)<<'\n';
    }
    g.close(); return 0;
}