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

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

int N, T, Tmin=-1;
int B[dim][2<<12-1];
bool Sel[dim];
int A[dim][dim];

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

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &T);
    for ( int k = 1; k <= T; k++ )
    {
        scanf("%d", &N);
        for ( int i = 1; i <= N; i++ )
            for ( int j = 1; j <= N; j++ )
                scanf("%d", &A[i][j]);
                
        Solve();
    }                
}    

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

int Minim(int a, int b)
{
    if ( a < b ) return a;
    return 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;
    
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= S; j++ )
            B[i][j] = 1000000;

    for ( int i = 1; i <= N; i++ )
        B[i][ 1<<(i-1) ] = 0;
   
  /*  for ( int k1 = 1; k1 <= S; k1++ )
    {     
        int minim = 1000000;
        for ( int i = 1; i <= N; 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; j++ )
                 {
                       if ( (k2>>(j-1))&1 == 0  ) continue;
                       if ( j == i ) continue;  
                       
                       if ( minim > A[i][j] + Maxim(B[j][k2],B[i][k1-k2]) ) 
                                minim = A[i][j] + Maxim(B[j][k2],B[i][k1-k2]);  
                 }
            }    
            if ( minim != 1000000 ) B[i][k1] = minim;
          }    
    }*/
    
    for ( int k1 = 1; k1 <= S; k1++ )
    {
        for ( int i = 1; i <= N; 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; 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]) ); 
                }             
            }
        }
    }
    
   /* for ( int i = 1; i <= N; i++, printf("\n") )
        for ( int j = 1; j <= S; j++ )
          printf("%d ", B[i][j]);*/

    printf("%d\n", B[1][S]);
}