#include <iostream>
#include <algorithm>

#define NMax 15
#define Inf 2000000000

using namespace std;

int N, Cost[NMax][NMax], Stack[NMax], Ordine[NMax];
int Time[NMax], S;

//int TestF[NMax], TestS[NMax];

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

void Back (int K)
{
    if (K==N+1)
    {
        bool Valid=false;
        for (int i=1; i<=N; ++i)
        {
            Ordine[i]=i;
            Time[i]=Inf;
            if (Stack[i]==1)
            {
                Valid=true;
            }
        }
        Time[1]=0;
        if (!Valid)
        {
            return;
        }
        do
        {
            for (int i=1; i<=N; ++i)
            {
                Time[i]=Inf;
            }
            Time[1]=0;
            for (int i=2; i<=N; ++i)
            {
                int Y=Ordine[i];
                int X=Stack[Ordine[i]];
                Time[Y]=Time[X]+Cost[X][Y];
                Time[X]+=Cost[X][Y];
            }
            int SCurent=0;
            for (int i=1; i<=N; ++i)
            {
                SCurent=Max (SCurent, Time[i]);
            }
            if (SCurent<S)
            {
                /*for (int i=2; i<=N; ++i)
                {
                    TestS[i]=Ordine[i];
                    TestF[i]=Stack[Ordine[i]];
                }*/
                S=SCurent;
            }
        }
        while (next_permutation (Ordine+2, Ordine+N+1));
    }
    else
    {
        for (int i=1; i<=N; ++i)
        {
            if (K!=i)
            {
                Stack[K]=i;
                Back (K+1);
                Stack[K]=0;
            }
        }
    }
}

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