#include<iostream>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

#include<cstdio>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

int main()

{

    int c,dp[][],a[][],n;

    scanf("%d",&c);

    while(c--)

    {

        scanf("%d",&n);

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

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

        {

            scanf("%d",&a[i][j]);

        }

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

            dp[n][i]=;

        }

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

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

        {

            dp[i][j]=max(dp[i+][j],dp[i+][j+])+a[i][j];

        }

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

    }

    return ;

}