#include <iostream>

const int MAXN = 12;
const int MAX = (1 << MAXN);
const int INF = 1e9;
int dp[MAXN][MAX], mr[MAXN][MAXN], logb2[MAX + 1];
int minim(int a, int b) {
    return a < b ? a : b;
}
int maxim(int a, int b) {
    return a > b ? a : b;
}
int main()
{
    FILE *fin, *fout;
    int t1, i1, n, i, l, c, mask, p, mask2, nod, b, mask3, x, y;
    //O(t * n^2 * 3^(n - 2))
    //fac un arbore cu muchiile pe care le aleg pentru raspunsul optim
    //si fac dp in care am radacina subarborelui fixat si masca cu subarborele sau
    //intr-un arbore rezultatul este maximul dintre drumul de la radacina la un nod + smua muchiilor de la acel nod la copii
    //deci acum aleg copii radacinei din subarbore fixata si cand fixez un fiu il aleg ca si cum ar fi primul fiu ca sa fie o recurenta usoara
    for (p = 1; p <= MAXN; p++) {
        logb2[(1 << p)] = p;
    }
    fin = fopen("cast.in", "r");
    fscanf(fin, "%d", &t1);
    fout = fopen("cast.out", "w");
    for (i1 = 0; i1 < t1; i1++) {
        fscanf(fin, "%d", &n);
        for (l = 0; l < n; l++) {
            for (c = 0; c < n; c++) {
                fscanf(fin, "%d", &mr[l][c]);
            }
        }
        p = (1 << n);
        for (i = 0; i < n; i++) {
            for (mask = 0; mask < p; mask++) {
                dp[i][mask] = INF;
            }
        }
        for (i = 0; i < n; i++) {
            dp[i][(1 << i)] = 0;
        }
        for (mask = 0; mask < p; mask++) {
            y = mask;
            while (y > 0) {
                nod = logb2[y & (-y)];
                //fixez acum noul fiu si subarborele sau, adica o submasca din mask ca mask este subarborele pe care vreau sa il fac
                mask3 = (mask ^ (1 << nod));
                for (mask2 = mask3; mask2 > 0; mask2 = ((mask2 - 1) & mask3)) {
                    x = mask2;//trec doar prin biti
                    while (x > 0) {
                        b = logb2[(x & (-x))];
                        //b este fiul cu subarborele fiind mask2(in subarbore este inclus si b, la fel cum si nod este inclus in mask)
                        dp[nod][mask] = minim(dp[nod][mask], maxim(dp[nod][mask ^ mask2], dp[b][mask2]) + mr[nod][b]);
                        x &= (x - 1);
                    }
                }
                y &= (y - 1);
            }
        }
        fprintf(fout, "%d\n", dp[0][p - 1]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}