#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream F("cast.in");
ofstream G("cast.out");

const int N = 12;

int t,n,vl,dp[N][1<<N],ct[N][N];
// dp[i][c] = timpul minim de transmisie de la nodul i in componenta sa c
// - ideea e ca transmiterea se face in forma unui arbore

int memo(int i,int c)
{
    if ( dp[i][c] < vl )
        return dp[i][c];

    vector<int> v;
    for (int b=0;b<n;++b)
        if ( b != i && (c & (1<<b)) )
            v.push_back(b);

    int ln = v.size();
    for (int cc=1;cc<(1<<ln);++cc)
    {
        int cc2 = 0;
        for (int b=0;b<ln;++b)
            if ( (cc & (1<<b)) )
                cc2 |= 1<<v[b];
        for (int b=0;b<n;++b)
            if ( cc2 & (1<<b) )
            {
                int left = memo(b,cc2);
                int right = memo(i,c^cc2);
                dp[i][c] = min(dp[i][c],max(left,right)+ct[i][b]);
            }
    }
    return dp[i][c];
}

int main()
{
    F>>t;
    for (int tt=1;tt<=t;++tt)
    {
        F>>n;
        for (int i=0;i<n;++i)
            for (int j=0;j<n;++j)
                F>>ct[i][j];
        memset(dp,0x3f,sizeof(dp));
        for (int i=0;i<n;++i)
            dp[i][1<<i] = 0;
        vl = dp[0][0];
        G<<memo(0,(1<<n)-1)<<'\n';
    }
}