#include <iostream>
using namespace std;
int main() {
// your code goes here
int a, b, arr[98][98], i, j, count=0, i_temp, j_temp, max, max1, max2;
cin>>a;
while(a--) {
arr[98][98]=0;
cin>>b;
count=0;
for(i=0; i<b; i++) {
if(count<b) count++;
for(j=0; j<count; j++) {
cin>>arr[i][j];
}
}
i_temp=i, j_temp=j;
for(; i>0; i--) {
j=j_temp;
for(; j>0; j--) {
max1=arr[i][j-1]+arr[i-1][j-1], max2=arr[i][j]+arr[i-1][j-1];
if(max1>max2) max=max1; else max=max2;
arr[i-1][j-1]=max;
}
j_temp=j_temp-1;
}
cout<<arr[0][0]<<endl;
//arr[100][100]=0;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCiBpbnQgYSwgYiwgYXJyWzk4XVs5OF0sIGksIGosIGNvdW50PTAsIGlfdGVtcCwgal90ZW1wLCBtYXgsIG1heDEsIG1heDI7CiBjaW4+PmE7CiB3aGlsZShhLS0pIHsKICBhcnJbOThdWzk4XT0wOwogIGNpbj4+YjsKICBjb3VudD0wOwogIGZvcihpPTA7IGk8YjsgaSsrKSB7CiAgIGlmKGNvdW50PGIpIGNvdW50Kys7CiAgIGZvcihqPTA7IGo8Y291bnQ7IGorKykgewogICAgY2luPj5hcnJbaV1bal07CiAgIH0KICB9CiAgaV90ZW1wPWksIGpfdGVtcD1qOwogIGZvcig7IGk+MDsgaS0tKSB7CiAgICBqPWpfdGVtcDsKICAgIGZvcig7IGo+MDsgai0tKSB7CiAgICAgICAgbWF4MT1hcnJbaV1bai0xXSthcnJbaS0xXVtqLTFdLCBtYXgyPWFycltpXVtqXSthcnJbaS0xXVtqLTFdOwogICAgICAgIGlmKG1heDE+bWF4MikgbWF4PW1heDE7IGVsc2UgbWF4PW1heDI7CiAgICAgICAgYXJyW2ktMV1bai0xXT1tYXg7CiAgICB9CiAgICBqX3RlbXA9al90ZW1wLTE7CiAgfQogIGNvdXQ8PGFyclswXVswXTw8ZW5kbDsKICAvL2FyclsxMDBdWzEwMF09MDsKIH0KIHJldHVybiAwOwp9