#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 13
#define INF 0x3f3f3f3f

int N;
int A[MAXN][MAXN];
int d[MAXN][1<<MAXN];
int NrBiti[1<<MAXN];

void read ()
{
    scanf ("%d", &N);
    
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            scanf (" %d", &A[i][j]);
}

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

int Get_Ans (int n, int mask)
{
    //printf ("%d\n", mask);
    int mask1, mask2, i;
    
    if (NrBiti[mask] == 1) return d[n][mask] = 0;
    if (d[n][mask]) return d[n][mask];
    
    int Min = INF, tmp;
    
    for (i = 0; i < N; ++ i)
        if (mask & (1 << i))
            for (mask1 = 0; mask1 <= mask; ++ mask1)
                if ((mask & mask1) == mask1 && (mask1 & (1 << i)))
                {
                    mask2 = mask - mask1;
                    if (mask2 & (1 << n))
                    {
                        tmp = A[n][i] + max (Get_Ans(i, mask1), Get_Ans(n, mask2));
                        Min = Min > tmp ? tmp : Min; 
                    }
                }
    
    return d[n][mask] = Min;
}

void solve ()
{
    memset (d, 0, sizeof (d));
    printf ("%d\n", Get_Ans (0, (1 << N) - 1));
}

int
 main ()
{
    freopen ("cast.in", "rt", stdin);
    freopen ("cast.out", "wt", stdout);
    
    
    for (int i = 1; i <= (1<<12); i <<= 1)
        NrBiti[i] = 1;
    int T;
    for (scanf ("%d", &T); T; -- T)
    {
        read ();
        solve ();
    }
    
    return 0;
}