/*
    Vreau sa calculez costul pentru arborele format din bitii de
  1 ai lui msk ce are radacina pe i, pe care il obtin combinand un
  subarbore cu un alt subarbore ce are radacina in j cu muchia i-j

                               i
                              / \
                             /   \
                            /     \
                           /       \
                        subarb1     j
                                    |
                                    |
                                 subarb2
*/
#include <cstdio>
#include <algorithm>

#define DIM 14
#define INF 1000000000
using namespace std;

int N, T, P[1 << DIM];
int D[1 << DIM][DIM], A[DIM][DIM];

inline int getSol (int msk, int i) {

    if (D[msk][i] != INF)
        return D[msk][i];

    int answer = INF, V[DIM], val, msk2, K;
    for (int j = 0; j < N; j ++) {

        if (!((msk >> j) & 1) || j == i)
            continue;

        val = msk - (1 << i) - (1 << j);

        K = 0;
        while (val) {
            V[K++] = (val & (-val));
            val -= (val & (-val));
        }

        for (int k = 0; k < (1 << K); k ++) {
            val = k; msk2 = (1 << j);

            while (val) {
                msk2 += V[P[(val & (-val))]];
                val -= (val & (-val));
            }

            answer = min (answer, A[i][j] + max (getSol (msk - msk2, i), getSol (msk2, j)));
        }
    }

    D[msk][i] = answer;

    return D[msk][i];
}

int main () {

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

    scanf ("%d", &T);

    for (int i = 0; i < DIM - 1; i ++)
        P[1 << i] = i;

    for (int t = 1; t <= T; t ++) {
        scanf ("%d", &N);

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

        for (int i = 1; i < (1 << N); i ++)
        for (int j = 0; j < N; j ++)
            D[i][j] = INF;

        for (int i = 0; i < N; i ++)
            D[1 << i][i] = 0;

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

    return 0;
}