sums-in-a-triangle.py

#!/bin/python3

import math
import os
import random
import re
import sys

if __name__ == '__main__':
    a = int(input().strip())
    for i in range(a):
        b = int(input().strip())
        arr = []
        for j in range(b):
            c = list(map(int, input().rstrip().split()))
            arr.append(c)
        
        for j in range(0, b-1):
            arr[j+1][0] += arr[j][0]
            for k in range(1, j+1):
                arr[j+1][k] += max(arr[j][k-1], arr[j][k])
            arr[j+1][j+1] += arr[j][j]
        print(max(arr[-1]))