#include <stdio.h>
#include <fstream>
#include <cstring>
using namespace std;

#define in "cast.in"
#define out "cast.out"
#define dim 13

int N, T, Tmin=-1;
int B[dim][8193], L[dim], sir[dim];
bool Sel[8193][dim];
int A[dim][dim];

int Maxim(int,int);
int Ok(int,int);
void Solve();

int main()
{
    int i, k1, j;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    memset(Sel,0,sizeof(Sel));
    
    for ( k1 = 1; k1 <= 8192; k1++ )
    {
        for ( i = 1; i <= 13; i++ )
            if ( (k1>>(i-1)) & 1 ) Sel[k1][i] = 1;
    }
    
    scanf("%d", &T);
    for ( ; T > 0; --T )
    {
        scanf("%d", &N);
        for ( i = 1; i <= N; i++ )
            for ( j = 1; j <= N; j++ )
                scanf("%d", &A[i][j]);
                
        Solve();
    }                
}    

inline int Minim(int a, int b)
{ return (a < b ? a : b); }

inline int Maxim(int a, int b)
{ return (a > b ? a : b); }


int Ok(int k1, int k2)
{
    for ( int i = 1; i <= N; i++ )
        if ( (k2>>(i-1))&1 ) 
             if ( !((k1>>(i-1))&1) ) return 0;
    
    return 1;  
}    

void Solve()
{
    int S = 1<<N;
    S -= 1;
    
    memset(B, 0x3f, sizeof(B) );
    
    for ( int i = 1; i <= N; i++ )
    {
        //B[i][ (1<<(i-1)) ] = 0;
        B[i][0] = 0;
    }
   
   /* for ( int k1 = 1; k1 <= S; ++k1 )
    {
        for ( int i = 1; i <= N && 1<<(i-1) <= k1; ++i )
        {
            if ( (k1>>(i-1))&1 == 0 ) continue;
            for ( int k2 = 1; k2 < k1; ++k2 )
            {
                if ( !Ok(k1,k2) ) continue;
                for ( int j = 1; j <= N && 1<<(j-1) <= k2; ++j )
                {
                    if ( (k2>>(j-1))&1 == 0 || i == j ) continue;
                    
                    B[i][k1] = Minim( B[i][k1], A[i][j] + Maxim(B[i][k1-k2],B[j][k2]) ); 
                }             
            }
        }
    }*/
    
   /* int size, Q, k, i, k1, k2, j, t;
    
    int pow=0;
    
    for ( k1 = 1; k1 <= S; ++k1 )
    {
          for ( i = 1; i <= N; ++i )
          {
              if ( (k1>>(i-1))&1 )
              {
                   if ( k1 == pow ) continue;
                   
                   size = 0;
                   pow = 1;
                   
                   for ( j = 1; pow <= k1 && j <= N; ++j )
                   {
                       pow = (1<<(j-1));
                       if ( i != j && (k1>>(j-1))&1 ) L[++size] = j;
                   }
                   
                   pow = (1<<size);
                   
                   for ( k2 = 1; k2 < pow; ++k2 )
                   {
                       Q = 0;
                       for ( t = 1; t <= size; ++t )
                           if ( (k2>>(t-1))&1 ) Q += (1<<(L[t]-1));
                       
                       if ( k1 < Q ) continue;
                       
                       int R = k1-Q;
                       
                       for ( t = 1; t <= size; ++t )
                       {
                           if ( B[i][k1] > A[i][L[t]] + Maxim(B[i][R],B[L[t]][Q])  ) B[i][k1] = A[i][L[t]] + Maxim(B[i][R],B[L[t]][Q]);
                          // B[i][k1] = Minim( B[i][k1], A[i][L[t]] + Maxim(B[i][R],B[L[t]][Q]) );
                       }                   
                   }
              }
          }
    } 
    */
    
    int k1, i, j, k2, t, Q1;
    int size=0, Q=0;
    
    for ( k1 = 1; k1 <= S; ++k1 )
        for ( i = 1; i <= N; ++i )
            if ( Sel[k1][i] )
            {
                 size = 0;
                 
                if ((k1 ^ (1 << (i - 1))) == 0)
                {
                	B[i][k1] = 0;
                    continue;
            	}
                 
                 for ( j = 1; j <= N; ++j )
                 {
                     if ( i != j && Sel[k1][j] ) L[++size] = j;  
                 }
                 
                 for ( k2 = 1; k2 < (1<<size); ++k2 )
                 {
                     Q = 0;
                     
                     for ( t = 1; t <= size; ++t )
                     {
                         if ( Sel[k2][t] ) Q += 1<<(L[t]-1);
                     }
                     
                     Q1 = k1^Q;
                     
                     for ( t = 1; t <= size; ++t )
                         B[i][k1] = Minim( B[i][k1], A[i][L[t]] + Maxim(B[L[t]][Q],B[i][Q1]) ); 
                 }
            }
            
   /* printf("\n");
     for ( int i = 1; i <= N; i++, printf("\n") )
        for ( int j = 1; j <= (1 << N) - 1; j++ )
            printf("%d ", B[i][j]);*/
   
   /*int i, j, mask, mask1, mask2, mask3, ct, nod, lim;
   
    memset(B, 0x3f, sizeof(B));
    for (i = 1; i <= N; ++i)
    	B[i][0] = 0;
	for (mask = 1; mask < 1 << N; ++mask)
        for (nod = 1; nod <= N; ++nod)
            if ((mask >> (nod - 1)) & 1)
            {
            	if ((mask ^ (1 << (nod - 1))) == 0)
                {
                	B[nod][mask] = 0;
                    continue;
            	}
            	ct = 0;
                for (i = 0; i < N; ++i)
                	if (nod != i + 1 && ((mask >> i) & 1))
                        sir[++ct] = i + 1;
                 
                // printf("%B ", ct);
                for (mask1 = 1; mask1 < 1 << ct; ++mask1)
                {
                    mask2 = 0;
                    for (i = 1; i <= ct; ++i)
                    	if ((mask1 >> (i - 1)) & 1)
                        	mask2 += 1 << (sir[i] - 1);
                   	
                    mask3 = mask ^ mask2;
                    for (i = 1; i <= ct; ++i);
                    {
                        B[nod][mask] = Minim(B[nod][mask], A[nod][sir[i]] + Maxim(B[sir[i]][mask2], B[nod][mask3]));
                       // w++;
                    }
                }
                //printf("%B %B -> %B\n", nod , mask, B[nod ][mask]);
            }*/
    
    printf("%d\n", B[1][S]);
}