#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

#define MAXN 12
#define MAX_CONF (1 << 12)
#define pb push_back
#define INF (1 << 30)

int T, N, A[MAXN][MAXN], Min[MAXN][MAX_CONF];
vector<int> G[MAX_CONF], V[MAX_CONF];

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

int solve(int x, int conf)
{
    if(Min[x][conf] != -1)
        return Min[x][conf];
        
    int conf2, y, i, j, aux, ret = INF;

    for(i = (int)(G[conf].size())-1; i >= 0; i--)
    {
        conf2 = G[conf][i];
        if( (conf2&(1<<x)) == 0 )
        {
            for(j = (int)(V[conf2].size())-1; j >= 0; j--)
            {
                y = V[conf2][j];
                aux = A[x][y]+max(solve(y, conf2), solve(x, conf^conf2));
                if(aux < ret)
                    ret = aux;
            }
        }
    }

    return Min[x][conf] = ret;
}

void preproc(void)
{
    int conf, conf2, i, j;
    
    for(conf = 0; conf < MAX_CONF; conf++)
     for(conf2 = 0; conf2 < MAX_CONF; conf2++)
      if( (conf2&conf) == conf2 )
        G[conf].pb(conf2);

    for(conf = 0; conf < MAX_CONF; conf++)
     for(i = 0; i < 12; i++)
      if(conf&(1<<i))
        V[conf].pb(i);
}

void ruleaza(void)
{
    int i, j, k;

    scanf("%d\n", &N);

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

    memset(Min, -1, sizeof(Min));
    
    for(i = 0; i < N; i++)
        Min[i][1<<i] = 0;

    printf("%d\n", solve(0, (1<<N)-1));
}

int main(void)
{
    freopen("cast.in", "rt", stdin);
    freopen("cast.out", "wt", stdout);

    scanf("%d\n", &T);

    preproc();
    
    while(T--)
        ruleaza();

    return 0;
}