#include <bits/stdc++.h>

using namespace std;

ifstream fin("cast.in");
ofstream fout("cast.out");

const int INF = 1000000000;

int t, n;
int c[15][15], dp[15][1 << 12];

int main() {
    fin >> t;

    for(; t; --t) {
        fin >> n;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                fin >> c[i][j];
            }
        }

        int lim = 1 << n;

        for(int i = 0; i < n; i++) {
            for(int mask = 0; mask < lim; mask++) {
                dp[i][mask] = INF;
            }

            dp[i][1 << i] = 0;
        }

        for(int lg = 2; lg <= n; lg++) {
            for(int mask = 0; mask < lim; mask++) {
                if(__builtin_popcount(mask) != lg) {
                    continue;
                }

                for(int root = 0; root < n; root++) {
                    if(!(mask & (1 << root))) {
                        continue;
                    }

                    int rest = mask ^ (1 << root);

                    for(int sub = rest; sub; sub = (sub - 1) & rest) {
                        int ramas = mask ^ sub;

                        for(int v = 0; v < n; v++) {
                            if(!(sub & (1 << v))) {
                                continue;
                            }

                            int val = c[root][v] + max(dp[v][sub], dp[root][ramas]);
                            dp[root][mask] = min(dp[root][mask], val);
                        }
                    }
                }
            }
        }

        fout << dp[0][lim - 1] << "\n";
    }

    return 0;
}