#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

ifstream F("cast.in");
ofstream G("cast.out");

const int oo = 0x3f3f3f3f; // 0x3f3f3f ?
const int ST = 12;

int N,M,T,D[ST][1<<ST],Cost[ST][ST];

#define have(conf) ( conf & (1<<i) )

int memo(int nod,int conf)
{
    if ( D[nod][conf] != oo )
        return D[nod][conf];

    vector<int> V;
    for (int i=0;i<N;++i)
        if ( i != nod && have(conf) )
            V.push_back(i);

    int lung = V.size();
    int stop = 1<<lung;

    for (int cnow=1;cnow<stop;++cnow)
    {
        int cnext=0;
        for (int i=0;i<lung;++i)
            if ( have(cnow) )
                cnext |= 1<<V[i];
        for (int i=0;i<N;++i)
            if ( have(cnext) )
            {
                int v1 = memo(i,cnext);
                int v2 = memo(nod,conf^cnext);
                v1 = max(v1,v2) + Cost[nod][i];
                if ( D[nod][conf] > v1 )
                    D[nod][conf] = v1;
            }

    }
    return D[nod][conf];
}

#undef have

int main()
{
    F>>T;
    while ( T-- )
    {
        F>>N;
        for (int i=0;i<N;++i)
            for (int j=0;j<N;++j)
                F>>Cost[i][j];
        memset(D,oo,sizeof(D));
        for (int i=0;i<N;++i)
            D[i][1<<i] = 0;
        G<<memo(0,(1<<N)-1)<<'\n';
    }
}