TSP

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 18;
const int mod = 1e9 + 7;


int dp[1 << N][N], n, s = 1, adj[N][N];

int solve(int mask, int u)
{

     //cout << mask << " ";
     if(mask == (1 << n) - 1)
     {

        if(adj[u][s]){
            //cout << "dkjfd";
            return adj[u][s];}
        return mod;
     }

     int& ans = dp[mask][u];
     if(ans != -1)return ans;
     ans = mod;
     for(int i = 1; i <= n; i++)
     {
        if(!(mask & (1 << (i-1))) && adj[u][i])
        {
            int a = adj[u][i] + solve(mask | (1 << (i-1)), i);
            ans = min(ans, a);
        }
     }
     //cout << u << " " << ans << "\n";
     return ans;
}



int main()
{
    fast;
    ll t;
    cin >> t ;
    while(t--){
    int m,a, b, c;
    cin >> n;
    n++;
    for(int i = 1 ; i <= n ; i++ ){
        for(int j = 1 ; j <= n ; j++ ){
            if(i == j)continue;
            cin >> c;
            adj[i][j]  = c;
        }
    }
    /*for(int i = 1 ;  i <= n ; i++ ){
        for(int j = 1 ; j <= n ;j++ ){
            cout << adj[i][j] << " ";
        }
        cout << "\n";
    }*/

    memset(dp, -1, sizeof(dp));
    cout << solve(1, 1) << "\n";

    memset(adj, 0, sizeof(adj));
    /*for(int i = 1 ;  i <= n ; i++ ){
        for(int j = 1 ; j <= n ;j++ ){
            adj[i][j] = 0;
        }
    }*/
    }





















    return 0;

}