c = int(raw_input())
while c>0:
    n = int(raw_input())
    a =[]
    get=[]
    for i in xrange(n):
        get = map(int,raw_input().split())
        a.append(get)

    for i in xrange(1,n):
        for j in xrange(i+1):
            if j==0:
                a[i][j]+=a[i-1][j]
            elif j==i:
                a[i][j]+=a[i-1][j-1]
            else:
                if a[i-1][j-1]>a[i-1][j]:
                    a[i][j]+=a[i-1][j-1]
                else:
                    a[i][j]+=a[i-1][j]

    large = 0
    for l in a[n-1]:
        if l>large:
            large = l
    print large
    c-=1