#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 = 16, 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 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] );

        int rad, st, nr, nst;
        CLRV( cst, -1 );
        n2 = (1 << n);
        for( st = 1 ; st < n2 ; st++ )
            for( rad = 0 ; rad < n ; rad++ )
            {
                int &res = cst[rad][st];
                if( st == (1 << rad) )
                {
                    cst[rad][st] = 0;
                    break;
                }

                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( cst[nr][nst], cst[rad][st ^ nst] ) 
                                            + a[rad][nr];
                            res = min( res, nval );
                        }   
            }
        printf( "%d\n", cst[0][n2 - 1] );
    }
    return 0;    
}