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

#define NMax 12
#define oo 1000000000

using namespace std;

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

inline int Memo (int X, int Conf)
{
    if (DP[X][Conf]!=-1) return DP[X][Conf];
    vector <int> Computers;
    for (int i=0; i<N; ++i)
    {
        if (Conf&(1<<i) and i!=X) Computers.push_back (i);
    }
    DP[X][Conf]=oo;
    for (int C=1; C<(1<<Computers.size ()); ++C)
    {
        int Conf1=0, Conf2=0;
        for (int i=0; i<(int)Computers.size (); ++i)
        {
            if (C&(1<<i)) Conf1|=(1<<Computers[i]);
        }
        Conf2=Conf^Conf1;
        for (int i=0; i<(int)Computers.size (); ++i)
        {
            if ((C&(1<<i)))
            {
                int Y=Computers[i];
                DP[X][Conf]=min (DP[X][Conf], max (Memo (Y, Conf1), Memo (X, Conf2))+Cost[X][Y]);
            }
        }
    }
    return DP[X][Conf];
}

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

void Init ()
{
    for (int i=0; i<N; ++i)
    {
        for (int j=0; j<(1<<N); ++j)
        {
            DP[i][j]=-1;
        }
        DP[i][1<<i]=0;
    }
}

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

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