#include<iostream>
#include<memory.h>
using namespace std;

int d[32][32];
int dp[32][32][32];
int n;

int dfs(int i, int j, int k, int m)
{
    if(dp[i][j][k] != 0)
        return dp[i][j][k];
    if(m == n)
        return 0;
    int ans = 999999;
    ans = dfs(m + 1, j, k, m + 1) + d[i][m + 1];
    ans = min(ans, dfs(i, m + 1, k, m + 1) + d[j][m + 1]);
    ans = min(ans, dfs(i, j, m + 1, m + 1) + d[k][m + 1]);
    dp[i][j][k] = ans;
    return ans;
}

int main()
{
    int caseNum;
    cin >> caseNum;
    for (int ca = 0; ca < caseNum;++ca)
    {
        cin >> n;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n;++i)
            for (int j = i+1; j <= n;++j)
                scanf("%d", &d[i][j]);
        int res = dfs(1, 1, 1, 1);
        cout << res << endl;
    }
}