#include <fstream>

using namespace std;
ifstream fin("cast.in");
ofstream fout("cast.out");
int t, n, cost[15][15], i, j, dp[15][5005], mask, submask;
int main()
{
    fin>>t;
    while(t--)
    {
        fin>>n;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                fin>>cost[i][j];
        dp[0][0]=0;
        for(mask=1; mask<(1<<n); mask++)
            for(i=1; i<=n; i++)
                if(mask&(1<<(i-1)))
                {
                    if(__builtin_popcount(mask)==1)
                        dp[i][mask]=0;
                    else
                    {
                        dp[i][mask]=1e9;
                        for(submask=mask; submask; submask=(submask-1)&mask)
                            if(!(submask&(1<<(i-1))))
                             for(j=1; j<=n; j++)
                                if(submask&(1<<(j-1)))
                                    dp[i][mask]=min(dp[i][mask], max(dp[i][mask^submask], dp[j][submask])+cost[i][j]);
                    }
                }
                else
                    dp[i][mask]=0;
        fout<<dp[1][(1<<n)-1]<<'\n';
    }
    return 0;
}