#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

MQozCjEKMiAxCjUgNCAz

1
3
1
2 1
5 4 3