#include <iostream>
#include <cstdio>
#define MAXN 12
#define inf 0x3f3f3f3f

using namespace std;

int t, n, cost[MAXN][MAXN];
int din[MAXN][1<<MAXN];

int solve(int nod, int mask)
{
    if (!mask) return 0;
    if (din[nod][mask] != inf) return din[nod][mask];
    for (int i = 0; i < n; i++)
        if (mask & (1<<i)) {
            int fara = mask ^ (1<<i);
            for (int nou = fara; ; nou = (nou-1) & fara) {
                din[nod][mask] = min(din[nod][mask], cost[nod][i] + max(solve(nod, nou), solve(i, fara^nou)));
                if (nou == 0)
                    break;
            }
        }
    return din[nod][mask];
}


int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);

    scanf("%d ", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d ", &cost[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < (1<<n); j++)
                din[i][j] = inf;
        int rez = solve(0, (1<<n)-2);
        printf("%d\n", rez);
    }

    return 0;
}