{{{
#!cplusplus
#include <iostream>
using namespace std;
const int N=110;
int a[N][N];
int f[N][N];
int n;
void Init()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<=i;j++)
			scanf("%d",&a[i][j]);
	memset(f,-1,sizeof(f));
}
int DP(int i,int j)
{
	int ans;
	if(f[i][j]>=0)
			return f[i][j];
	if(i==n-1)
		ans=a[i][j];
	else
	{
		if(DP(i+1,j)>DP(i+1,j+1))
			ans=a[i][j]+DP(i+1,j);
		else
			ans=a[i][j]+DP(i+1,j+1);		
	}
	f[i][j]=ans;
	return f[i][j];
}
int main()
{
	int test;
	cin>>test;
	while(test-->0)
	{
		Init();
		printf("%d\n",DP(0,0));
	}
}

}}}

{{{
#!cplusplus
//非递规 dp  written by czy
#include <stdio.h>
#include <memory.h>

int tower[102][102];
int tmax[102][102];

int max(int &a, int &b){
    return a>b?a:b;
}

int main(){
    int Case;
    scanf("%d",&Case);
        while(Case--){
            int tHeight;
            scanf("%d", &tHeight);
            for(int i = 1; i <= tHeight; i++){
                for(int j = 1; j <= i; j++){
                    scanf("%d", &tower[i][j]);
                }
            }
            memset(tmax,0,101*101*4);

            //dp
            for(int k = tHeight; k > 0; k--){
                for(int l = 1; l <= k; l++)
                    if(k==tHeight)
                        tmax[k][l] = tower[k][l];
                    else
                        tmax[k][l] = tower[k][l] + max(tmax[k+1][l],tmax[k+1][l+1]);
            }
            printf("%d\n", tmax[1][1]);
        }
    

    return 0;
}

}}}