#include <iostream>
using namespace std;
class tri_st{
    public:
    int tri_temp[100][100];
    tri_st(){
        tri(input_num());
    }
    int input_num(){
        int n,i;
        scanf("%d",&n);
        for(i=0;i<n;i++){
            for(int q=0;q<=i;q++){
                scanf("%d",&tri_temp[i][q]);
            }
        }
        return i-1;
    }
    int tri(int y){
        for(int i=0;tri_temp[y][i]>=1;i++){
            tri_temp[y][i]=max(tri_temp[y][i]+tri_temp[y+1][i],tri_temp[y][i]+tri_temp[y+1][i+1]);
        }
        if(y==0){
            printf("%d\n",tri_temp[0][0]);
        }
        else{
            tri(y-1);
        }
    }
};
int main() {
    int test;
    scanf("%d",&test);
    for(int i=0;i<test;i++){
        tri_st();
    }
    return 0;
}