#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 12
#define INF 0x3f3f3f3f
#define FIN "cast.in"
#define FOUT "cast.out"

int N, T, V[MAX_N], nv, D[MAX_N][MAX_N], A[MAX_N][1<<MAX_N];

void bkt(int lv, int cfg, int msk)
{
    int *i, *j;

    if (lv == nv)
    {
        for (i = V; i < V+nv; i++)
            for (j = V; j < V+nv; j++)
            {
                if (!(cfg&(1<<*j))) continue;
                A[*i][cfg] = min(A[*i][cfg], D[*i][*j]+max(A[*j][msk], A[*i][cfg-msk]));
            }
        return;
    }

    bkt(lv+1, cfg, msk);
    bkt(lv+1, cfg, msk|(1<<V[lv]));
}

int main(void)
{
    int i, j;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    for (scanf("%d", &T); T; T--)
    {
        scanf("%d", &N);
        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                scanf("%d", D[i]+j);

        for (i = 0; i < N; i++)
            for (j = 0; j < (1<<N); j++)
                A[i][j] = INF;
        
        for (i = 1; i < (1<<N); i++)
        {
            for (nv = j = 0; j < N; j++)
                if (i&(1<<j)) V[nv++] = j;
            if (nv == 1) { A[V[0]][1<<V[0]] = 0; continue; }
            bkt(0, i, 0);
        }
        printf("%d\n", A[0][(1<<N)-1]);
    }

    return 0;
}