#include <iostream>
#include<bits/stdc++.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
using namespace std;
int t,n, t1, t2;
int a[102][102]= {0}; //= new int *[n];
//int cache[102][102];
int solve(int i, int j)
{
cout<<"\n i="<<i<<"j="<<j<<"n="<<n<<"a[i][j]"<<a[i][j];
//cout<<"\ncahce original at i , j"<<cache[i][j];
if(i>=n)
return 0;
// if(cache[i][j] > 0)
// { cout<<"\n returning cache i ="<<i<<" j= "<<j<<"cache value= "<<cache[i][j];
// return cache[i][j];
// }
t1= solve(i+1,j);
t2= solve(i+1,j+1);
t= max(t1,t2)+a[i][j];
cout<<"\nt1="<<t1<<"t2="<<t2<<"t="<<t;
// cache[i][j]=t;
// cout<<"\n putting in cache t"<<cache[i][j];
return t;
}
int main() {
int test=0, i, j;
scanf("%d", &test);
while(test--)
{
scanf("%d", &n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%d", &a[i][j]);
printf("ans =%d\n",solve(0,0));
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIG1heChhLGIpICgoYSkgPiAoYikgPyAoYSkgOiAoYikpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCB0LG4sIHQxLCB0MjsgCmludCBhWzEwMl1bMTAyXT0gezB9OyAvLz0gbmV3IGludCAqW25dOwovL2ludCBjYWNoZVsxMDJdWzEwMl07CgppbnQgc29sdmUoaW50IGksIGludCBqKQp7Cgljb3V0PDwiXG4gaT0iPDxpPDwiaj0iPDxqPDwibj0iPDxuPDwiYVtpXVtqXSI8PGFbaV1bal07IAoJIC8vY291dDw8IlxuY2FoY2Ugb3JpZ2luYWwgYXQgaSAsIGoiPDxjYWNoZVtpXVtqXTsKCWlmKGk+PW4pCglyZXR1cm4gMDsgCgkKLy8JaWYoY2FjaGVbaV1bal0gPiAwKQovLwl7ICBjb3V0PDwiXG4gcmV0dXJuaW5nIGNhY2hlIGkgPSI8PGk8PCIgaj0gIjw8ajw8ImNhY2hlIHZhbHVlPSAiPDxjYWNoZVtpXVtqXTsKLy8JCXJldHVybiBjYWNoZVtpXVtqXTsKLy8JfQoJCgkgdDE9IHNvbHZlKGkrMSxqKTsgCgkgdDI9IHNvbHZlKGkrMSxqKzEpOyAKCSB0PSBtYXgodDEsdDIpK2FbaV1bal07CgkgY291dDw8IlxudDE9Ijw8dDE8PCJ0Mj0iPDx0Mjw8InQ9Ijw8dDsKLy8JIGNhY2hlW2ldW2pdPXQ7Ci8vCSAgY291dDw8IlxuIHB1dHRpbmcgaW4gY2FjaGUgdCI8PGNhY2hlW2ldW2pdOwoJIHJldHVybiB0Owp9CgppbnQgbWFpbigpIHsKaW50IHRlc3Q9MCwgaSwgajsKc2NhbmYoIiVkIiwgJnRlc3QpOyAKd2hpbGUodGVzdC0tKQp7CglzY2FuZigiJWQiLCAmbik7IAoJCglmb3IoaT0wO2k8bjtpKyspCiAgICBmb3Ioaj0wO2o8PWk7aisrKQoJIHNjYW5mKCIlZCIsICZhW2ldW2pdKTsKCiBwcmludGYoImFucyA9JWRcbiIsc29sdmUoMCwwKSk7CgkKfQoJcmV0dXJuIDA7Cn0=