#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

#define REP( i, n )         for( (i) = 0 ; (i) < (n) ; (i)++ )
#define IREP( i, n )        for( (i) = (n) - 1 ; (i) >= 0 ; (i)-- )
#define REPV( i, a, b )     for( (i) = (a) ; (i) <= (b) ; (i)++ )
#define IREPV( i, a, b )    for( (i) = (b) ; (i) >= (a) ; (i)-- )
#define REPIT( it, x )      for( (it) = (x).begin( ) ; (it) != (x).end( ) ; (it)++ )
#define ALL( x )            (x).begin( ), (x).end( )
#define MP                  make_pair
#define PB                  push_back
#define CLR( x )            memset( (x), 0, sizeof( x ) )
#define CLRV( x, v )        memset( (x), (v), sizeof( x ) )
#define CPY( y, x )         memcpy( (y), (x), sizeof( x ) )
#define X                   first
#define Y                   second

typedef long long Ll;
typedef pair< int, int > Pii;
typedef pair< Ll, Ll > Pll;
typedef vector< int > Vi;
typedef vector< Ll > Vl;
typedef vector< string > Vs;

const int MAXN = 12, MAXST = (1 << MAXN);
const int INF = 0x1f1f1f1f;
const Ll INFL = 0x1f1f1f1f1f1f1f1fLL;
const double EPS = 1e-9;
int n, n2;
int a[MAXN][MAXN];
int cst[MAXN][MAXST];   

int go( int rad, int st )
{
    //fprintf( stderr, "Go: %d %x\n", rad, st );
    int &res = cst[rad][st];
    if( res != -1 )
        return res;
    if( st == (1 << rad) )
        return (res = 0);

    int nst, nr;
    res = INF;
    for( nr = 0 ; nr < n ; nr++ )
        if( nr != rad && (st & (1 << nr)) != 0 )
            for( nst = 0 ; nst < n2 ; nst++ )
                if( (st & nst) == nst &&
                    (nst & (1 << rad)) == 0 &&
                    (nst & (1 << nr)) != 0 )
            {
                int nval = max( go( nr, nst ), go( rad, st ^ nst ) ) 
                                + a[rad][nr];
                res = min( res, nval );
            }   
    return res;
}

int main( )
{
    freopen( "cast.in", "r", stdin );
    freopen( "cast.out", "w", stdout );

    int nt;
    scanf( "%d", &nt );
    while( nt-- )
    {
        int i, j;
        scanf( "%d", &n );
        for( i = 0 ; i < n ; i++ )
            for( j = 0 ; j < n ; j++ )
                scanf( "%d", &a[i][j] );

        CLRV( cst, -1 );
        n2 = (1 << n);
        int res = go( 0, n2 - 1 );
        printf( "%d\n", res );
    }
    return 0;    
}