#include <bits/stdc++.h>

using namespace std;

const int nmax = 12;
const int inf = 0x3f3f3f3f;

int i , j , k , n;
int a[nmax][nmax];
int dp[nmax][1<<nmax];

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

    int tests;
    for (scanf("%d", &tests); tests; tests--)
    {
        scanf("%d", &n);
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                scanf("%d", &a[i][j]);

        memset(dp , inf , sizeof(dp));

        for (i = 0; i < n; ++i) dp[i][1<<i] = 0;
        for (int conf = 1; conf < (1 << n); ++conf)
            for (j = 0; j < n; ++j)
            {
                if (conf & (1 << j)); else continue;

                int mask = conf ^ (1 << j);
                for (int mask2 = mask; mask2 ; mask2 = (mask2 - 1) & mask)
                {
                    for (k = 0; k < n; ++k)
                    {
                        if (mask2 & (1 << k)); else continue;
                        dp[j][conf] = min(dp[j][conf] , a[j][k] + max(dp[j][conf^mask2] , dp[k][mask2]));
                    }
                }
            }

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

    return 0;
}