#include<stdio.h>
#define max 100
int a[max][max];
int main(){
int c,d,t=0,e,n,m,f,g,h,i;
scanf("%d",&c);// test cases
for(d=1;d<=c;d++){
scanf("%d",&e);// no. of input rows
for(m=0;m<e;m++){
for(n=0;n<=m;n++)
scanf("%d",&a[m][n]);
}
for(f=e-1;f>0;f--){// logic
for(g=0;g<f;g++){
h= a[f][g]+ a[f-1][g];
i= a[f][g+1] + a[f-1][g];
if(h>i)
a[f-1][g]= h;
else
a[f-1][g]= i;
}
}
printf("%d\n",a[0][0]);
t++;
}
return 0;
}
ICAgICNpbmNsdWRlPHN0ZGlvLmg+CiAgICAjZGVmaW5lIG1heCAxMDAKICAgIGludCBhW21heF1bbWF4XTsKICAgIGludCBtYWluKCl7CiAgICBpbnQgYyxkLHQ9MCxlLG4sbSxmLGcsaCxpOwogICAgIAogICAgc2NhbmYoIiVkIiwmYyk7Ly8gdGVzdCBjYXNlcwogICAgZm9yKGQ9MTtkPD1jO2QrKyl7CiAgICBzY2FuZigiJWQiLCZlKTsvLyBuby4gb2YgaW5wdXQgcm93cwogICAgZm9yKG09MDttPGU7bSsrKXsKICAgIGZvcihuPTA7bjw9bTtuKyspCiAgICBzY2FuZigiJWQiLCZhW21dW25dKTsKICAgIH0KICAgIGZvcihmPWUtMTtmPjA7Zi0tKXsvLyBsb2dpYwogICAgZm9yKGc9MDtnPGY7ZysrKXsKICAgIGg9IGFbZl1bZ10rIGFbZi0xXVtnXTsKICAgIGk9IGFbZl1bZysxXSArIGFbZi0xXVtnXTsKICAgIGlmKGg+aSkKICAgIGFbZi0xXVtnXT0gaDsKICAgIGVsc2UKICAgIGFbZi0xXVtnXT0gaTsKICAgIH0KICAgIH0KICAgICBwcmludGYoIiVkXG4iLGFbMF1bMF0pOwogICAgdCsrOwogICAgfQogICAgcmV0dXJuIDA7CiAgICB9Cg==