import java.io.* ;
class SumInTriangle {
int [ ] [ ] arr= new int [ 100 ] [ 100 ] ;
int testcases
= Integer .
parseInt ( br.
readLine ( ) ) ;
while ( testcases> 0 )
{
int n
= Integer .
parseInt ( br.
readLine ( ) ) ; for ( int i= 0 ; i< n; i++ )
{
for ( int j= 0 ; j<= i; j++ )
arr
[ i
] [ j
] = Integer .
parseInt ( br.
readLine ( ) ) ; }
for ( int i= n- 2 ; i>= 0 ; i-- )
{
for ( int j= 0 ; j<= i; j++ )
{
arr[ i] [ j] += arr[ i+ 1 ] [ j] > arr[ i+ 1 ] [ j+ 1 ] ? arr[ i+ 1 ] [ j] : arr[ i+ 1 ] [ j+ 1 ] ;
}
}
System .
out .
printf ( "%d\n " ,arr
[ 0 ] [ 0 ] ) ; testcases--;
}
}
}
aW1wb3J0IGphdmEuaW8uKjsKCgpjbGFzcyBTdW1JblRyaWFuZ2xlIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBhcmdzW10pIHRocm93cyBJT0V4Y2VwdGlvbnsKICAgIEJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKICAgIGludFtdW10gYXJyPW5ldyBpbnRbMTAwXVsxMDBdOwoKICAgIGludCB0ZXN0Y2FzZXMgPUludGVnZXIucGFyc2VJbnQoYnIucmVhZExpbmUoKSk7CgogICAgd2hpbGUodGVzdGNhc2VzPjApCiAgICB7CgogICAgaW50IG4gPSBJbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkpOwogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgIHsKICAgIGZvcihpbnQgaj0wO2o8PWk7aisrKQogICAgYXJyW2ldW2pdPSBJbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkpOwogICAgfQogICAgZm9yKGludCBpPW4tMjtpPj0wO2ktLSkKICAgIHsKICAgIGZvcihpbnQgaj0wO2o8PWk7aisrKQogICAgewogICAgYXJyW2ldW2pdKz1hcnJbaSsxXVtqXT5hcnJbaSsxXVtqKzFdP2FycltpKzFdW2pdOmFycltpKzFdW2orMV07CiAgICB9CiAgICB9CiAgICBTeXN0ZW0ub3V0LnByaW50ZigiJWRcbiIsYXJyWzBdWzBdKTsKICAgIHRlc3RjYXNlcy0tOwogICAgfQoKCiAgICB9Cgp9