/*
* Author: Geeza
*/

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define pb push_back
#define fin(a, n) for(int i = a; i < n; i++)
#define fjn(a, n) for(int j = a; j < n; j++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

using namespace std;

const double PI = acos(-1);
const int N = 1e6+5;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353, inf = 1e6;

string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
char dc[] = {'D', 'L', 'R', 'U'};

ll n;
vector<vector<ll>> grid;
ll dp[1<<11][12]; // mask, lst

ll calc(ll mask, ll lst) {
    if (mask == (1<<n)-1) {
        return grid[lst][0];
    }

    ll &ret = dp[mask][lst];
    if (~ret)return ret;
    ret = oo;

    for (int i = 1; i < n; i++) {
        if ((mask>>i)&1ll)continue;
        ret = min(ret, calc(mask|(1ll<<i), i)+grid[lst][i]);
    }
    return ret;
}

void solve() {
    cin >> n; ++n;
    grid = vector<vector<ll>>(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i==j)continue;
            cin>>grid[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << calc(1, 0) << "\n";
}

int main() {
    FAST;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int tt = 1; cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}