#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

using namespace std;

#define MEM(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define debug printf("!/m")

#define L 150

#define MAX(a,b) a>b?a:b

int tower[L][L];

int dp[L][L];

int main()

{

          int t,i,j;

          sf("%d",&t);

          while(t--)

          {

                    int n;

                    sf("%d",&n);

                    MEM(dp,);

                    for(i = ;i<n;i++)

                    {

                              for(j = ;j<=i;j++)

                              {

                                        sf("%d",&tower[i][j]);

                              }

                    }

                    for(i = n-;i>=;i--)

                    {

                              for(j = ;j<=i;j++)

                              {

                                        int t = MAX(dp[i+][j],dp[i+][j+]);

                                        dp[i][j] = t+tower[i][j];

                              }

                    }

                    pf("%d\n",dp[][]);

          }

    return ;

}