#include<stdio.h>
int main()
{
	int row,a[100][100],t,k,sum,s;
	scanf("%d",&t);
	while(t>0)
	{	
	scanf("%d\n",&row);
	int i=0,j=0;
		sum=0;
while(i<row)
	{
	while(j<=i)
	{
		scanf("%d",&a[i][j]);
		j++;
 
	}
	j=0;
	i++;
	}
	sum=a[0][0]+a[1][0];
	i=1; j=0;int l=0;
	 while(i+1<row)
	{
		l++;
		k=j;
		if(a[i+1][j+1]>=a[i+1][j])
		{
			s=a[i+1][j+1];
			sum=sum+s;
			j=i;
		}
		else if(a[i+1][k+1]<a[i+1][k])
		{
			sum=sum+a[i+1][k];
			j=i-1;
		}
	i++;
	}
	printf("%d\n",sum);
t--;
} 
return 0;
}
 
 

I2luY2x1ZGU8c3RkaW8uaD4KaW50IG1haW4oKQp7CglpbnQgcm93LGFbMTAwXVsxMDBdLHQsayxzdW0sczsKCXNjYW5mKCIlZCIsJnQpOwoJd2hpbGUodD4wKQoJewkKCXNjYW5mKCIlZFxuIiwmcm93KTsKCWludCBpPTAsaj0wOwoJCXN1bT0wOwp3aGlsZShpPHJvdykKCXsKCXdoaWxlKGo8PWkpCgl7CgkJc2NhbmYoIiVkIiwmYVtpXVtqXSk7CgkJaisrOwogCgl9CglqPTA7CglpKys7Cgl9CglzdW09YVswXVswXSthWzFdWzBdOwoJaT0xOyBqPTA7aW50IGw9MDsKCSB3aGlsZShpKzE8cm93KQoJewoJCWwrKzsKCQlrPWo7CgkJaWYoYVtpKzFdW2orMV0+PWFbaSsxXVtqXSkKCQl7CgkJCXM9YVtpKzFdW2orMV07CgkJCXN1bT1zdW0rczsKCQkJaj1pOwoJCX0KCQllbHNlIGlmKGFbaSsxXVtrKzFdPGFbaSsxXVtrXSkKCQl7CgkJCXN1bT1zdW0rYVtpKzFdW2tdOwoJCQlqPWktMTsKCQl9CglpKys7Cgl9CglwcmludGYoIiVkXG4iLHN1bSk7CnQtLTsKfSAKcmV0dXJuIDA7Cn0KIAo=

Mgo4CjEKNSAxCjIgMyAxCjEgNSA2IDEKMSAyIDEgMyA4CjcgOCA5IDQgMiAzCjQgNSAxIDMgMSAyIDYKNSA1IDUgNSA1IDUgNSA1CjMKNQo1IDYKNSA2IDc=

2
8
1
5 1
2 3 1
1 5 6 1
1 2 1 3 8
7 8 9 4 2 3
4 5 1 3 1 2 6
5 5 5 5 5 5 5 5
3
5
5 6
5 6 7