#include <iostream>

#define NMax 15
#define Inf 2000000000

using namespace std;

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

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

int Memo (int Conf, int X)
{
    if (Best[Conf][X]<Inf)
    {
        return Best[Conf][X];
    }
    int Computers[NMax];
    for (int i=0; i<=N; ++i)
    {
        Computers[i]=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;
    }
    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];
}

int main()
{
    freopen ("cast.in", "r", stdin);
    freopen ("cast.out", "w", stdout);
    int T;
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        scanf ("%d", &N);
        int n=(1<<N);
        for (int i=1; i<n; ++i)
        {
            for (int j=0; j<N; ++j)
            {
                Best[i][j]=Inf;
            }
        }
        for (int i=0; i<N; ++i)
        {
            for (int j=0; j<N; ++j)
            {
                scanf ("%d", &Cost[i][j]);
            }
        }
        printf ("%d\n", Memo (n-1, 0));
    }
    return 0;
}