#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int INF = 200000;

int Query(int n, const vector<vector<int>> &cost)
{
    vector<vector<int>> dp(n, vector<int>(1 << n, INF));
    for(int i = 0; i < n; ++i)
        dp[i][1 << i] = 0;
    for(int mask = 0; mask < (1 << n); ++mask)
    {
        vector<int> v;
        for(int i = 0; i < n; ++i)
            if((mask & (1 << i)) != 0)
                v.push_back(i);
        for(int tMask = 0; tMask < (1 << v.size()); ++tMask)
        {
            int fromMask = 0;
            for(int i = 0; i < v.size(); ++i)
                if((tMask & (1 << i)) != 0)
                    fromMask |= (1 << v[i]);

            for(auto start:v)
            {
                if((fromMask & (1 << start)) != 0)
                    continue;
                for(auto to:v)
                {
                    if((fromMask & (1 << to)) == 0)
                        continue;
                    dp[start][mask] = min(dp[start][mask], max(dp[start][mask ^ fromMask], dp[to][fromMask]) + cost[start][to]);
                }
            }
        }
    }
    return dp[0][(1 << n) - 1];
}

int main()
{
    ifstream in("cast.in");
    ofstream out("cast.out");
    int t;
    in >> t;
    while(t--)
    {
        int n;
        in >> n;
        vector<vector<int>> cost(n, vector<int>(n));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                in >> cost[i][j];
        out << Query(n, cost) << "\n";
    }
    in.close();
    out.close();
    return 0;
}