#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#define inf 0x3f3f3f3f
using namespace std;
int din[1<<12][14];
int N;
int T;
short cost[24][24];

int main()
{

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

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

                    {
                        //if(!((1<<i)&(newstare^stare)))
                            //printf("!");
                        //if((1<<i)&(newstare^stare))
                        if((1<<k)&newstare)
                        {//printf("!");
                        int maxi;
                        if(din[newstare^stare][i]>din[newstare][k])

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