#include <bits/stdc++.h>

using namespace std;

const int nmax = 15;
const int inf = 1000000000;

int c[nmax][nmax] , d[1 << nmax][nmax];
vector < int > tmp;
int n , tests , mask , submask , tmpmask , _i , _j , b , s , nr , i , j;

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

for (scanf("%d" , &tests) ; tests ; --tests)
{
    scanf("%d" , &n);

    memset(c , 0 , sizeof(c));
    memset(d , 0 , sizeof(d));

    for(i = 0 ; i < n ; ++i)
    for(j = 0 ; j < n ; ++j)
    scanf("%d" , &c[i][j]);

    for (mask = 1 ; mask < (1 << n) ; ++mask)
    {
        tmp.clear();
        for (i = 0 ; i < n ; ++i)
        if (mask & (1 << i)) tmp.push_back(i);

        nr = tmp.size();
        if (nr == 1)
        {
            d[mask][tmp[0]] = 0;
            continue;
        }

        for (_i = 0 ; _i < tmp.size() ; ++_i)
        {
            b = tmp[_i];
            if ((mask & 1) && b > 0) continue;

            d[mask][b] = inf;
            for (tmpmask = 1 ; tmpmask < (1 << nr) ; ++tmpmask)
            {
                submask = 0;
                for (i = 0 ; i < nr ; ++i)
                if (tmpmask & (1 << i)) submask += (1 << tmp[i]);

                if (submask & (1 << b)) continue;

                for (_j = 0 ; _j < tmp.size() ; ++_j)
                {
                    s = tmp[_j];
                    if (submask & (1 << s))
                    d[mask][b] = min(d[mask][b] , c[b][s] + max(d[mask - submask][b] , d[submask][s]));
                }
            }
        }
    }

    cout << d[(1 << n) - 1][0] << '\n';
}

return 0;
}