#include <cstdio>
#include <string>

int a[14][14], n;
int dp[(1<<14)+1][14];

inline int min(int a,int b)
{
    if(a<b) return a;
    return b;
}

inline int max(int a,int b)
{
    if(a>b) return a;
    return b;
}

inline int solve(int nd, int cnf)
{

   // printf("%d %d\n",nd, cnf);
    int nr=0;
    for(int j=1;j<=n;++j)
	if(cnf&(1<<(j-1)))++nr;
    if(nr==1) return 0;
    if(dp[cnf][nd]!=-1) return dp[cnf][nd];


    // dp[cnf][nd]=0x3f3f3f3f;
    
    int i,j,ok,cn;
    int mn=0x3f3f3f3f;
    for(i=1; i<=(1<<(n))-1;++i)
    {
	  if(i&(1<<(nd-1)))continue;
	ok=1;

	for(j=1;j<=n;++j)
	    if((cnf&(1<<(j-1)))==0)
		if(i&(1<<(j-1))) {ok=0;break;}

	if(ok==0) continue;
	cn=0;
	for(j=1;j<=n;++j)
    if(!(i&(1<<(j-1))) && ( cnf&(1<<(j-1))))cn|=(1<<(j-1));
	  //  if(i&(1<<(j-1)))cn|=(1<<(j-1));
	 //  else cn&=~(1<<(j-1));
	  
      // 	printf("(%d %d %d\n",cnf, i,cn); 
	int v1=solve(nd, cn);
	

	for(j=1;j<=n;++j)
	    if(i&(1<<(j-1)))
		{ if(j==nd)continue;
		    //printf("%d %d %d\n", solve(j,i), solve(nd, cn),a[nd][j]);
	//	    printf("%d\n",solve(j,i)+a[nd][j]);
		    mn=min(mn, a[nd][j]+max(solve(j, i), solve(nd, cn)));
		    //dp[cnf][nd]=min(dp[cnf][nd],  a[nd][j]+max(solve(j, i), solve(nd, cn)));

	    	}
	

    }

    dp[cnf][nd]=mn;
return dp[cnf][nd];


}

int main()
{
    int T,i,j;
    freopen("cast.in","r",stdin);
    freopen("cast.out","w",stdout);
    scanf("%d\n", &T);
    while(T--)
    {
	scanf("%d\n", &n);
	for(i=1;i<=n;++i)
	    for(j=1;j<=n;++j)scanf("%d ", &a[i][j]);
	memset(dp,-1, sizeof(dp));
	printf("%d\n",solve(1, (1<<n)-1));
/*
	for(i=1;i<=n;++i)
	{
	    for(j=1;j<=(1<<(n))-1;++j)printf("%d ", dp[i][j]);
	    printf("\n");
	}


	printf("%d\n",(1<<n)-1);
	*/
    }

    return 0;
}