#include <fstream>

using namespace std;
int B[(1<<12) + 5];
int a[12][12], x[12], unu, doi, all, n, t;
int D[1<<12][12];
void back(int pas) {
    for (int i=0;i<3;i++) {
        x[pas] = i;

        if (i == 1)
            unu += (1<<pas);
        if (i == 2)
            doi += (1<<pas);

        all = (unu | doi);

        if (B[all])
            D[all][ B[all]-1 ] = 0;
        else {
            for (int x = 0; x<=pas; x++)
                if ((unu >> x) & 1)
                    for (int y=0; y<=pas; y++)
                        if ((doi >> y) & 1) {
                            D[all][x] = min(D[all][x], max(D[unu][x], D[doi][y]) + a[x][y]);
                            D[all][y] = min(D[all][y], max(D[unu][x], D[doi][y]) + a[y][x]);
                        }
        }
        if (pas < n-1)
            back(pas+1);

        if (i == 1)
            unu -= (1<<pas);
        if (i == 2)
            doi -= (1<<pas);
    }
}

int main () {
    ifstream fin ("cast.in");
    ofstream fout("cast.out");

    for (int i=0;i<=12;i++) {
        B[1<<i] = i+1;
    }

    for (fin>>t;t--;) {
        fin>>n;
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                fin>>a[i][j];

        unu = 0;
        doi = 0;
        for (int i=0; i<(1<<n); i++)
            for (int j=0; j<n;j++)
                D[i][j] = 1000000000;

        back(0);
        fout<<D[(1<<n)-1][0]<<"\n";
    }

    return 0;
}