#include <fstream>

using namespace std;

constexpr int MAX_N = 12;
constexpr int INF = 0x3f3f3f3f;

int dp[1 << MAX_N][MAX_N]; // dp[i][masca] -> pleaca din i si acopera nodurile din masca
int cost[MAX_N][MAX_N];
int lg[1 << MAX_N];

int main() {
    ifstream cin("cast.in");
    ofstream cout("cast.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int num_tests; cin >> num_tests;
    lg[1] = 0;
    for (int i = 2; i < 4096; i += 1) {
        lg[i] = lg[i >> 1] + 1;
    }
    while (num_tests--) {
        int n; cin >> n;
        for (int i = 0; i < n; i += 1) {
            for (int j = 0; j < n; j += 1) {
                cin >> cost[i][j];
            }
        }
        const int mask_limit = (1 << n);
        for (int i = 0; i < mask_limit; i += 1) {
            if (i & (i - 1)) {
                for (int j = i; j; j = j & (j - 1)) {
                    const int node = lg[j & -j];
                    const int sub_mask = i ^ (1 << node);
                    dp[i][node] = INF;
                    for (int sub_set = sub_mask; sub_set; sub_set = (sub_set - 1) & sub_mask) {
                        for (int sub_set_node = sub_set; sub_set_node; sub_set_node = sub_set_node & (sub_set_node - 1)) {
                            const int k = lg[sub_set_node & -sub_set_node];
                            const int cover_cost = dp[i ^ sub_set][node] > dp[sub_set][k] ? dp[i ^ sub_set][node] // acorera restul nodurilor cu node
                                                                                          : dp[sub_set][k];       // acopera subset-ul pornind din k
                                                                                                                  // in paralel
                            if (dp[i][node] > cost[node][k] + cover_cost) {
                                dp[i][node] = cost[node][k] + cover_cost;
                            }
                        }
                    }
                }
            } else {
                dp[i][lg[i]] = 0;
            }
        }
        cout << dp[mask_limit - 1][0] << '\n';
    }
    cin.close();
    cout.close();
    return 0;
}