# include <cstdio>
//# include <cstring>
# include <vector>

using namespace std;

# define input "cast.in"
# define output "cast.out"

# define max 12
# define maxV 1<<max
int c[max][max];
long d[maxV][max];
int n,i,T,j,nr;
long mask,mask2;

# define minim(a,b) (a<b?a:b)
# define maxim(a,b) (a>b?a:b)

long calcmin()
{
     memset(d,1,sizeof(d));
     
     for(i=0;i<n;i++)
		 d[1<<i][i] = 0;
         
     for(mask = 1;mask < (1<<n);mask++)
     {
         for(i=0;i<n;i++)
         {
             if(mask&(1<<i))
			 {
				 nr = 0;
                 for(j=0;j<n;j++)
					 if(mask&(1<<j))
                         nr++;
                 if(nr == 1)
                     continue;
				 for(mask2 = 1;mask2 <= mask;mask2++)
				 {
					int ok = 1;
					 for(j=0;j<n;j++)
						 if(mask2&(1<<j) && !(mask & (1<<j)))
						 {
							ok = 0;
							break;
						 }
					 if(ok)
					 for(j=0;j<n;j++)
						 if(mask2&(1<<j))
							 d[mask][i]  = minim(d[mask][i],maxim(d[mask-mask2][i],d[mask2][j]) + c[i][j]);
                 }
             }
         }
     }
     
	 return d[(1<<n)-1][0];
}

int main()
{
    freopen(input,"r",stdin);
    freopen(output,"w",stdout);
    
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
           for(j=0;j<n;j++)
               scanf("%d",&c[i][j]);
               
        printf("%ld\n",calcmin());
    }
    
    return 0;
}