#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#define inf 0x3f3f3f3f
using namespace std;

int main()
{
short din[1<<12][14];
int N;
int T;
short cost[24][24];
short i,j,k,stare,newstare;
freopen("cast.in","r",stdin);
freopen("cast.out","w",stdout);
scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(i=0;i<N;++i)
            for(j=0;j<N;++j)
                scanf("%d",&cost[i][j]);
        for(i=0;i<N;++i)
            for(j=0;j<(1<<N);++j)
                din[j][i]=inf;
        for(int i=0;i<N;++i)
            din[1<<i][i]=0;
        for(stare=1;stare<(1<<N);++stare)
        {
            for(i=0;i<N;++i)
            {

                if((1<<i)&stare)
                for(k=0;k<N;++k)
                {
                if(i!=k)
                for (newstare=stare-(1<<i); newstare; newstare=stare&(newstare-1))
                {
                if(newstare!=stare)

                      //  if((1<<i)&(newstare^stare))
                        if((1<<k)&newstare)
                        {
                        din[stare][i]=min(din[stare][i],(short)(cost[i][k]+(short)max((short)din[newstare^stare][i],(short)din[newstare][k])));
                        }
                    }
                }
            }
        }
        //if(din[0][((1<<N)-1)])
         //   printf("5\n");
          //  else
        printf("%d\n",din[((1<<N)-1)][0]);
    }
    return 0;
}