#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
//#include <bits/stdc++.h>
#define in fin
#define out fout
#define oo (LLONG_MAX - 120000)

using namespace std;
using ll = long long;

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

int n;
ll cost[15][15];
ll dp[32770][15];

void backt(int mask, int root, int mask1, int p){
    if(p == n){
        // cout << "mask = " << mask << " Mask1 = " << mask1 << '\n';
        int mask2 = (mask - mask1);
        for(int i = 0; i < n; i++){
            if( (mask1 & (1 << i)) == 0 ) continue;
            dp[mask][root] = min( dp[mask][root], max( dp[mask1][i] + cost[root][i],
                                                        dp[mask2][root] + cost[root][i] ) );
        }
        return;
    }

    if( (mask & (1 << p)) != 0 ){
        backt(mask, root, mask1 + (1 << p), p + 1);
    }
    backt(mask, root, mask1, p + 1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; in >> t;
    for(int ii = 0; ii < t; ii++){
        in >> n;

        for(int i = 0; i < 15; i++){
            for(int j = 0; j < 15; j++) cost[i][j] = 0;
        }

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

        for(int i = 0; i <= (1 << n + 1); i++){
            for(int j = 0; j <= n + 1; j++) dp[i][j] = oo;
        }

        for(int i = 0; i < n; i++){
            dp[0][i] = 0;
            dp[(1 << i)][i] = 0;
        }
        
        for(int mask = 0; mask < (1 << n); mask++){
            for(int root = 0; root < n; root++){
                if( (mask & (1 << root)) == 0 ) continue;
                backt(mask, root, 0, 0);
            }
        }

        ll mini = oo;
        for(int i = 0; i < n; i++){
            mini = min(mini, dp[(1 << n) - 1][i]);
        }

        out << mini << '\n';
    }

    return 0;
}