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