#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==

MgozCjEKMiAxCjEgMiAzCjQgCjEgCjEgMiAKNCAxIDIKMiAzIDEgMSA=

2
3
1
2 1
1 2 3
4 
1 
1 2 
4 1 2
2 3 1 1