#include <stdio.h>
 
int main()
{
int t;
int n,max,sum,x,k;
int a[100][100];
int i,j;
scanf("%d",&t);
if(t>1000||t<1)
return 0;
while(t--){
max=0;
//printf("-------------- INPUT ------------------\n");
scanf("%d",&n);
if(n>100||n<1)
continue;
for(i=1;i<=n;i++){
for(j=0;j<i;j++){
scanf("%d",&a[i-1][j]);
if(a[i-1][j]>99||a[i-1][j]<0)
return 0;
}
}
//printf("------------- OUTPUT -------------------\n");
if(n==1){
printf("%d\n",a[0][0]);
continue;
}
for(k=n-1;k>=0;k--){
for(j=0;j<k;j++){
sum=0;
for(i=k;i>=0;i--){
if(i==k){
sum+= a[i][j]>a[i][j+1]? a[i][j]:a[i][j+1];
//printf("----adding %d,--- j=%d,---i=%d\n",sum,j,i);
}
else{
x= j<=i? 0:(j-i);
//printf("----adding %d,--- j=%d,---i=%d\n",a[i][j-x],j,i);
sum+= a[i][j-x];
}
}
if(sum>max)
max=sum;
//printf(" Sum %d = %d\n",j,sum);
}
}
printf("%d\n",max);
//******************************
}
return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiAKaW50IG1haW4oKQp7CmludCB0OwppbnQgbixtYXgsc3VtLHgsazsKaW50IGFbMTAwXVsxMDBdOwppbnQgaSxqOwpzY2FuZigiJWQiLCZ0KTsKaWYodD4xMDAwfHx0PDEpCnJldHVybiAwOwp3aGlsZSh0LS0pewptYXg9MDsKLy9wcmludGYoIi0tLS0tLS0tLS0tLS0tIElOUFVUIC0tLS0tLS0tLS0tLS0tLS0tLVxuIik7CnNjYW5mKCIlZCIsJm4pOwppZihuPjEwMHx8bjwxKQpjb250aW51ZTsKZm9yKGk9MTtpPD1uO2krKyl7CmZvcihqPTA7ajxpO2orKyl7CnNjYW5mKCIlZCIsJmFbaS0xXVtqXSk7CmlmKGFbaS0xXVtqXT45OXx8YVtpLTFdW2pdPDApCnJldHVybiAwOwp9Cn0KLy9wcmludGYoIi0tLS0tLS0tLS0tLS0gT1VUUFVUIC0tLS0tLS0tLS0tLS0tLS0tLS1cbiIpOwppZihuPT0xKXsKcHJpbnRmKCIlZFxuIixhWzBdWzBdKTsKY29udGludWU7Cn0KZm9yKGs9bi0xO2s+PTA7ay0tKXsKZm9yKGo9MDtqPGs7aisrKXsKc3VtPTA7CmZvcihpPWs7aT49MDtpLS0pewppZihpPT1rKXsKc3VtKz0gYVtpXVtqXT5hW2ldW2orMV0/IGFbaV1bal06YVtpXVtqKzFdOwovL3ByaW50ZigiLS0tLWFkZGluZyAlZCwtLS0gaj0lZCwtLS1pPSVkXG4iLHN1bSxqLGkpOwp9CmVsc2V7Cng9IGo8PWk/IDA6KGotaSk7Ci8vcHJpbnRmKCItLS0tYWRkaW5nICVkLC0tLSBqPSVkLC0tLWk9JWRcbiIsYVtpXVtqLXhdLGosaSk7CnN1bSs9IGFbaV1bai14XTsKfQp9CmlmKHN1bT5tYXgpCm1heD1zdW07Ci8vcHJpbnRmKCIgU3VtICVkID0gJWRcbiIsaixzdW0pOwp9Cn0KcHJpbnRmKCIlZFxuIixtYXgpOwovLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgp9CnJldHVybiAwOwp9

MQozCjEKMiAxCjUgNCAz

1
3
1
2 1
5 4 3