#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int t;
	cin>>t;
	for(int k=1;k<=t;++k)
	{
		int n;
		cin>>n;
		vector< vector<int> > a ( n, vector<int>(n,0));
		vector< vector<int> > b ( n, vector<int>(n,0));
		for(int i=0;i<n;++i)
			for(int j=0;j<=i;++j)
				cin>>a[i][j];
		b[0][0]=a[0][0];
		for(int i=0;i<n-1;++i)
			for(int j=0;j<=i;++j)
			{
				b[i+1][j]=max(b[i+1][j],b[i][j]+a[i+1][j]);
				b[i+1][j+1]=max(b[i+1][j+1],b[i][j]+a[i+1][j+1]);
			}
		int ans=b[n-1][0];
		for(int i=0;i<n;++i)
			ans=max(ans,b[n-1][i]);
		cout<<ans<<endl;
	}
}