#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 12, INF = 0x3f3f3f3f;

int N, Cost[NMAX][NMAX], Dp[NMAX][1 << NMAX], T;

int Solve(int Root, int Conf)
{
    if(Dp[Root][Conf] != INF) return Dp[Root][Conf];

    vector<int> V;
    for(int i = 0; i < N; ++ i)
        if(Root != i && (Conf & (1 << i)))
            V.push_back(i);

    for(int i = 0; i < (1 << V.size()); ++ i)
    {
        int SubTreeConf = 0;
        for(int j = 0; j < V.size(); ++ j)
            if(i & (1 << j))
                SubTreeConf |= (1 << V[j]);

        for(int j = 0; j < V.size(); ++ j)
            if(i & (1 << j))
                Dp[Root][Conf] = min(Dp[Root][Conf], Cost[Root][V[j]] + max(Solve(V[j], SubTreeConf), Solve(Root, Conf ^ SubTreeConf)));
    }
    return Dp[Root][Conf];
}

int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);

    scanf("%i", &T);
    for(; T; T --)
    {
        scanf("%i", &N);
        for(int i = 0; i < N; ++ i)
        {
            for(int j = 0; j < N; ++ j) scanf("%i", &Cost[i][j]);
            for(int j = 0; j < (1 << N); ++ j) Dp[i][j] = INF;
            Dp[i][1 << i] = 0;
        }
        printf("%i\n", Solve(0, (1 << N) - 1));
    }
}