#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 p[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]);
}

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