#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define MAXN 13
#define INF 0x3f3f3f3f
#define TIP(x) cout << __LINE__ << ": " #x << " = " << x << endl

int N;
int A[MAXN][MAXN];
int d[MAXN][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]);
}

int Get_Ans (int n, int mask)
{
    //TIP(mask);
    int mask1, mask2, i;
    
    if (mask == 0) return d[n][0] = 0;
    if (d[n][mask]) return d[n][mask];
    
    int Min = INF, tmp, a, b;
    for (mask1 = 0; mask1 <= (mask >> 1); ++ mask1)
        if ((mask & mask1) == mask1)
        {
            mask2 = mask - mask1;
            for (i = 0; i < N; ++ i)
                if (mask1 & (1 << i))
                {
                    a = Get_Ans(i, mask1 - (1<<i)); 
                    if (a + A[n][i] > Min) continue;
                    b = Get_Ans(n, mask2);
                    tmp = A[n][i] + (a > b ? a : b);
                    //TIP (tmp); TIP (n); TIP(i);
                    Min = Min > tmp ? tmp : Min; 
                }
                else if (mask2 & (1 << i))
                {
                    
                    b = Get_Ans(n, mask1);
                    if (b + A[n][i] > Min) continue;
                    a = Get_Ans(i, mask2 - (1<<i)); 
                    tmp = A[n][i] + (a > b ? a : b);
                    //TIP (tmp); TIP (n); TIP(i);
                    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;
}