#include"stdio.h"
#define INF 0x7fffffff
typedef struct
{
	int car[3];
	int total;
}state;
int main()
{
	int i,j,k,n,m,time[31][31],t,s;
	state f[35][3];
	
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
		scanf("%d",&time[i][j]);
		
		f[0][0].total=0;f[0][1].total=0;f[0][2].total=0;
		f[1][0].total=time[0][1];f[1][1].total=time[0][1];f[1][2].total=time[0][1];
		f[1][0].car[0]=1;f[1][0].car[1]=0;f[1][0].car[2]=0;
		f[1][1].car[0]=0;f[1][1].car[1]=1;f[1][1].car[2]=0;
		f[1][2].car[0]=0;f[1][2].car[1]=0;f[1][2].car[2]=1;
		for(i=2;i<n;i++)
		for(j=0;j<3;j++)
		{
			for(k=0,s=INF;k<3;k++)
			if(f[i-1][k].total+time[f[i-1][k].car[j]][i]<s)
			{
				s=f[i-1][k].total+time[f[i-1][k].car[j]][i];
				m=k;
			}
			f[i][j].car[0]=f[i-1][m].car[0];
			f[i][j].car[1]=f[i-1][m].car[1];
			f[i][j].car[2]=f[i-1][m].car[2];
			f[i][j].car[j]=i;
			f[i][j].total=s;
		}
		
		for(i=0,s=INF;i<3;i++)
		if(s>f[n-1][i].total)s=f[n-1][i].total;
		
		printf("%d\n",s);
	}
	return 1;
}