#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)
{
    int mask1, mask2, i;
    
    if (mask == 0) return d[n][0] = 0;
    if (NrBiti[mask]) return d[n][mask] = A[n][NrBiti[mask]];
    if (d[n][mask]) return d[n][mask];
    
    int Min = INF, tmp;
    for (mask1 = 0; mask1 <= mask; ++ mask1)
        if ((mask & mask1) == mask1)
        {
            mask2 = mask - mask1;
            for (i = 0; i < N; ++ i)
                if (mask1 & (1 << i))
                {
                    tmp = A[n][i] + max (Get_Ans(i, mask1 - (1<<i)), 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) - 2));
}

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