#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>


int arr[300][300]={-1};
int cp[300][300];

long long a,b,c;
int num;

int main()
{
    int i,j;
    cin>>a;




    while(num<a){
        cin>>b;
                for(i=0; i<b; i++){
                    for(j=0; j<=i; j++)
                    {
                        cin>>arr[i][j];
                    }
                }
        for(i=0; i<b; i++){
            for(j=0; j<=i; j++)
            {
                if(i==0)
                    cp[i][j]=arr[i][j];     //첫번째는 그냥 복사
                else{                       //첫번째행이 아니라면
                    if(j==0)                //첫번째 인자는 그냥 더해서 내려옴
                        cp[i][j]=arr[i][j];
                    else if(i==j)           //마지막 인자도 그냥 더함
                        cp[i][j]=cp[i-1][j-1]+arr[i][j];    //마지막인자도 비교없이 그냥 더함
                    else
                        cp[i][j]=max(cp[i-1][j-1]+arr[i][j],cp[i-1][j]+arr[i][j]);          //그 중간에 있는건 최대값 함수 써서 구함
                }
            }       
        }
            sort(&cp[i-1][0],&cp[i-1][j]);
            cout<<cp[i-1][j-1]<<endl;
            num++;
    }
}