#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#define inf 0x3f3f3f3f
using namespace std;
int din[1<<12][12];
int N;
int T;
int cost[24][24];
char op[1<<12][12];
int nr;
int main()
{
freopen("cast.in","r",stdin);
freopen("cast.out","w",stdout);
scanf("%d",&T);
    while(T--)
    {   ++nr;
        scanf("%d",&N);
        for(int i=0;i<N;++i)
            for(int j=0;j<N;++j)
                scanf("%d",&cost[i][j]);
        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<<i)&(newstare^stare))
                        if((1<<k)&newstare)
                        {
                        if(din[stare][i]>cost[i][k]+max(din[newstare^stare][i],din[newstare][k]))
                            din[stare][i]=cost[i][k]+max(din[newstare^stare][i],din[newstare][k]);
                        if(op[stare][i]!=nr){
                            op[stare][i]=nr;
                             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]);
    }
}