#include <cstdio>
#include <algorithm>

using namespace std;

int cost[15][15], i,j, mask,msk, dp[4100][13], t, n;

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

    scanf("%d", &t);

    while(t--)
    {
        scanf("%d", &n);
        for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            scanf("%d", &cost[i][j]);

        for(mask=1; mask<(1<<n); ++mask)
        for(i=0; i<n; ++i)
        if(mask&(1<<i))
        {
            if(mask==(1<<i))
            {
                dp[mask][i] = 0;
                continue;
            }
            dp[mask][i] = (1<<30);

            for(msk = mask^(1<<i); msk; msk = (msk-1)&(mask^(1<<i)) )
            for(j=0; j<n; ++j)
            if(msk&(1<<j))
                dp[mask][i] = min( dp[mask][i], cost[i][j] + max( dp[mask^msk][i], dp[msk][j] ) );
        }

        printf("%d\n", dp[mask-1][0]);
    }

    return 0;
}