#include <cstdio>
#include <algorithm>
#include <cstring>

#define NMax 13
#define oo 1000000000

using namespace std;

int T, N, Cost[NMax][NMax], Best[(1<<NMax)][NMax];

inline int Memo (int Conf, int X)
{
    if (Best[Conf][X]!=-1)
    {
        return Best[Conf][X];
    }
    int Computers[NMax]; Computers[0]=0;
    for (int i=0; i<N; ++i)
    {
        if (Conf&(1<<i)) Computers[++Computers[0]]=i;
    }
    if (Computers[0]==1)
    {
        Best[Conf][X]=0; return 0;
    }
    Best[Conf][X]=oo;
    int NConf=(1<<Computers[0]);
    for (int C=1; C<NConf; ++C)
    {
        int Conf1=0, Conf2=0;
        for (int i=0; i<Computers[0]; ++i)
        {
            if (C&(1<<i)) Conf1+=(1<<Computers[i+1]);
        }
        if (Conf1&(1<<X)) Conf1-=(1<<X);
        Conf2=Conf-Conf1;
        for (int Comp=0; Comp<N; ++Comp)
        {
            if ((Conf1&(1<<Comp)) and (Comp!=X))
            {
                Best[Conf][X]=min (Best[Conf][X], max (Memo (Conf1, Comp), Memo (Conf2, X))+Cost[X][Comp]);
            }
        }
    }
    return Best[Conf][X];
}

void Read ()
{
    scanf ("%d", &N);
    for (int i=0; i<N; ++i)
    {
        for (int j=0; j<N; ++j)
        {
            scanf ("%d", &Cost[i][j]);
        }
    }
    memset (Best, -1, sizeof (Best));
}

void Print ()
{
    printf ("%d\n", Memo ((1<<N)-1, 0));
}

int main()
{
    freopen ("cast.in", "r", stdin);
    freopen ("cast.out", "w", stdout);
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        Read ();
        Print ();
    }
    return 0;
}