#include <fstream>
#include <vector>
#include <cstring>

#define INF 0x3f3f3f3f
#define MAX 12

using namespace std;

int N, M, T;
int dp[MAX][(1 << MAX)], V[MAX][MAX];

int solve(int nod, int conf)
{
    if(dp[nod][conf] != INF) return dp[nod][conf];
    vector<int> W;
    for(int i = 0; i < N; i++)
        if((conf & (1 << i)) && i != nod)
            W.push_back(i);
    for(int conf2 = 1; conf2 < (1 << W.size()); conf2++)
    {
        int resultingConf = 0;
        for(int i = 0; i < W.size(); i++)
            if(conf2 & (1 << i))
                resultingConf |= (1 << W[i]);
        for(int i = 0; i < N; i++)
            if(resultingConf & (1 << i))
                dp[nod][conf] = min(dp[nod][conf],
                                    max(solve(nod, conf ^ resultingConf), solve(i, resultingConf)) + V[nod][i]);
    }
    return dp[nod][conf];
}

int main()
{
    ifstream in("cast.in"); ofstream out("cast.out");
    for(in>>T; T; T--) {
        in>>N;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                in>>V[i][j];
        memset(dp, INF, sizeof(dp));
        for(int i = 0; i < N; i++) dp[i][(1 << i)] = 0;
        out<<solve(0, (1 << N) - 1)<<"\n";
    } in.close(); out.close();
    return 0;
}