#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#define inf 0x3f3f3f3f
using namespace std;
int din[1<<12][14];
int N;
int T;
int 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 newstare=stare; newstare; newstare=stare&(newstare-1))
                {
                if(newstare!=stare)
                for(int k=0;k<N;++k)
                    {
                        if(((1<<k)&newstare)&&((1<<i)&(newstare^stare)))
                        {
                        din[stare][i]=min(din[stare][i],cost[i][k]+max(din[newstare^stare][i],din[newstare][k]));
                        }
                    }
                }
            }
        }
        //if(din[0][((1<<N)-1)])
         //   printf("5\n");
          //  else
        printf("%d\n",din[((1<<N)-1)][0]);
    }
}