#include <bits/stdc++.h>
#define maxN 13
#define maxC (1 << 12) + 1
#define inf 1000000
using namespace std;
int t, n, cost[maxN][maxN], dp[maxC][maxN];
void read()
{
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; ++ i)
        for (j = 0; j < n; ++ j)
            scanf("%d", &cost[i][j]);
}
void solve()
{
    int i, j, k, conf;
    for (i = 1; i < (1 << n); ++ i)
        for (j = 0; j < n; ++ j)
            if (i & (1 << j))
            {
                if (i == (1 << j))
                {
                    dp[i][j] = 0;
                    break;
                }
                dp[i][j] = inf;
                int cf = i ^ (1 << j);
                for (conf = cf; conf > 0; conf = cf & (conf - 1))
                    for (k = 0; k < n; ++ k)
                        if (conf & (1 << k))
                        {
                            int val = max(dp[conf][k] + cost[j][k], dp[i ^ conf][j] + cost[j][k]);
                            if (dp[i][j] > val)
                                dp[i][j] = val;
                        }
            }
}
void write()
{
    printf("%d\n", dp[(1 << n) - 1][0]);
}
int main()
{
    freopen("cast.in", "r", stdin);
    freopen("cast.out", "w", stdout);
    scanf("%d", &t);
    while (t --)
    {
        read();
        solve();
        write();
    }
    return 0;
}