def helper(rows, triangle):
    for row in range(rows - 2, -1, -1):
        for col in range(len(triangle[row])):
            triangle[row][col] += max(triangle[row + 1][col], 
                                      triangle[row + 1][col + 1])
    
    return triangle[0][0]

for _ in range(int(input())):
        rows = int(input())
        triangle = []

        for _ in range(rows):
            row = list(map(int, input().split()))
            triangle.append(row)
        
        result = helper(rows, triangle)
        print(result)