#include<bits/stdc++.h>
using namespace std;
ifstream fin("cast.in");
ofstream fout("cast.out");

const int INF = 2000000;

int N, T, Dp[(1<<15)][20], Cst[20][20], B[20];

int solve( int mask, int x ){

    if( Dp[mask][x] != INF )
        return Dp[mask][x];

    for( int y = 0; y < N; y++ ){

        if( y == x || ( ((mask>>y) & 1) == 0 ) )
            continue;

        int mask0 = mask - (1<<x) - (1<<y), nr = 0;
        for( int i = 0; i < N; i++ ){
            if( ((mask0>>i) & 1) == 1 )
                B[nr++] = i;
        }

        for( int conf = 0; conf < (1<<nr); conf++ ){
            int mask1 = (1<<y);
            for( int i = 0; i < nr; i++ )
                if( ((conf>>i) & 1 ) == 1 )
                    mask1 += (1<<B[i]);
            Dp[mask][x] = min( Dp[mask][x], Cst[x][y] + max( solve( mask - mask1, x ), solve( mask1, y ) ) );
        }
    }
    return Dp[mask][x];
}

int main(){

    fin >> T;
    while( T-- ){
        fin >> N;
        for( int i = 0; i < N; i++ )
            for( int j = 0; j < N; j++ )
                fin >> Cst[i][j];

        for( int i = 0; i < N; i++ )
            for( int mask = 0; mask < (1<<N); mask++ )
                Dp[mask][i] = INF;
        for( int i = 0; i < N; i++ )
            Dp[(1<<i)][i] = 0;

        fout << solve( (1<<N) - 1, 0 ) << "\n";
    }

    return 0;
}