#include <iostream> //2084 hdu c++
#include<string.h>
using namespace std;
int a[105][105],b[105][105];
int n;
int max(int x, int y)
{ return x>y?x:y ; }

int f(int i,int j)
{
if(b[i][j]!=-1) return b[i][j];
return b[i][j]=a[i][j]+max(f(i+1,j),f(i+1,j+1));
}

int main()
{
int i,j,c;
cin>>c;
while(c--)
{
cin>>n ;
for(i=0;i<n;i++)
for(j=0;j<=i;j++) cin>>a[i][j];
memset(b,-1,sizeof(b));
for(j=0;j<n;j++) b[i-1][j]=a[i-1][j];
cout<<f(0,0)<<endl;
}

}