def max_path(n,triangle):
    temp=[[] for _ in range(n)]
    for k in triangle[-1]:
        temp[-1].append(k)
    for i in range(n-2,-1,-1):
        for j in range(i+1):
            temp[i].append(triangle[i][j]+max(temp[i+1][j],temp[i+1][j+1]))
    return temp[0][0]
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    triangle=[]
    for i in range(n):
        triangle.append(list(map(int,input().strip().split())))
    print(max_path(n,triangle))