// Maximum-TNT

#include <iostream>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <fstream>
#include <climits>

using namespace std;

#define cin fin
#define ivec_t vector<long long>
#define imat_t vector<ivec_t>
#define im3_t vector<imat_t>
#define im4_t vector<im3_t>

const int BUFSIZE = 1024;
const int INF=INT_MAX;
ifstream fin("magazine.txt");
imat_t g_dist;
int g_n;

long long Solve()
{
    im3_t table(g_n+1,imat_t(g_n,ivec_t(g_n,INF)));
    table[0][0][0] = 0;
    for(int i = 1; i < g_n ; i++)
    {
	for(int j = 0 ; j < i ; j++)
	    for(int k = j ; k < i ; k++)
	    {
		table[i][j][k] = min(table[i][j][k],table[i-1][j][k] + g_dist[i-1][i]);
		table[i][k][i-1] = min(table[i][k][i-1],table[i-1][j][k]+g_dist[j][i]);
		table[i][j][i-1] = min(table[i][j][i-1],table[i-1][j][k]+g_dist[k][i]);
	    }
    }
    long long ans = INF;
    for(int i = 0 ; i < g_n ; i++)
	for(int j = 0 ; j < g_n ; j++)
	    ans = min(table[g_n-1][i][j],ans);
    return ans;
}

void FloydWarshall()
{
    for(int i = 0 ; i < g_n ; i++)
	for(int j = 0 ; j < g_n ; j++)
	    for(int k = 0 ; k < g_n ; k++)
		if(g_dist[j][k] > g_dist[j][i]+g_dist[i][k])
		    g_dist[j][k] = g_dist[j][i]+g_dist[i][k];
}

int main()
{
    int case_num;
    cin >> case_num;
    while(case_num--)
    {
	cin >> g_n;
	g_dist.assign(g_n,ivec_t(g_n,INF));
	for(int i = 0 ; i < g_n ; i++)
	{
	    g_dist[0][0] = 0;
	    for(int j = i+1 ; j < g_n ; j++)
	    {
		cin >> g_dist[i][j];
		g_dist[j][i] = g_dist[i][j];
	    }
	}
	FloydWarshall();
	cout << Solve() << endl;
    }
    return 0;
}