#include <fstream>
using namespace std;

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

const int N = 12;

int t,n,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 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];
        for (int i=0;i<n;++i)
            dp[i][0] = dp[i][1] = 1<<30;
        dp[0][1] = 0;
        int ans = 1<<30;
        for (int c=2;c<(1<<n);++c)
            for (int i=0;i<n;++i)
            {
                dp[i][c] = 1<<30;
                int bits = 0;
                for (int b=0;b<n;++b)
                    bits += int( ((1<<b)&c) != 0 );
                if ( bits == 1 && (1<<i) == c )
                    dp[i][c] = 0;
                if ( bits == 1 )
                    break;
                bits--;
                for (int c2=0;c2<(1<<bits);++c2)
                {
                    int cf = 0,nw = 0;
                    for (int b=0;b<n;++b)
                        if ( b != i && ((1<<b)&c) )
                        {
                            if ( c2 & (1<<nw) )
                                cf += (1<<b);
                            ++nw;
                        }
                    for (int b=0;b<n;++b)
                        if ( b != i && ((1<<b)&cf) )
                            dp[i][c] = min(dp[i][c],max(dp[i][c^cf],dp[b][cf])+ct[i][b]);
                }
            }
        G<<dp[0][(1<<n)-1]<<'\n';
    }
}