#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 NrB[1<<MAXN];

void preproc ()
{
    for (int i = 1; i <= (1<<12); ++ i)
        for (int j = 1; j <= i; j <<= 1)
            if (i & j) ++ NrB[i];
}

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

int Get_Ans (int n, int mask)
{
    int mask1, mask2, i, j;
    
    if (mask == 0) return d[n][0] = 0;
    if (d[n][mask]) return d[n][mask];
    
    int Min = INF, tmp, a, b, cnt, p = (1<<NrB[mask]);
    
    for (j = 1; j < p; ++ j)
    {
        mask1 = cnt = 0;
        for (i = 0; i < N && cnt < NrB[mask]; ++ i)
        {
            if (mask & (1 << i) && j & (1 << cnt))
                mask1 += (1 << i);
            if (mask & (1 << i))
                ++ cnt;
        }
        mask2 = mask - mask1;
        
        b = Get_Ans(n, mask2); 
        for (i = 0; i < N; ++ i)
            if (mask1 & (1 << i))
            {
                a = Get_Ans(i, mask1 - (1<<i));
                //if (b + A[n][i] > Min) continue;
                tmp = A[n][i] + (a > b ? a : b);
                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);
    
    preproc ();
    
    int T;
    for (scanf ("%d", &T); T; -- T)
    {
        read ();
        solve ();
    }
    
    return 0;
}