def f(i,j):
    m=t[i][j]
    return i==l-1 and[m,]or [x+m for x in f(i+1,j)+f(i+1,j+1)]
c=input()
r=[]
for i in range(c):
    l=input()
    t=[]
    for i in range(l):
        t+=[(map(int,raw_input().split()))]
    r+=[max(f(0,0))]
for i in r:
    print i

t = [] #
l = 0 #

def f(i,j,s):
    m=t[i][j]
    if i==l-1:
        return m+s
    else:
        return max(f(i+1,j,m+s),f(i+1,j+1,m+s))

def main():
    global strNum, inpData, l, t #
    for i in range(1): #
        strNum = 0 #
        c=int(inpData[strNum])#input()
        strNum += 1 #
        r=[]
        for i in range(c):
            l=int(inpData[strNum])#input()
            strNum += 1 #
            t=[]
            for i in range(l):
                t+=[[int(x) for x in inpData[strNum].split()]]#raw_input().split()))]
                strNum += 1 #
            r+=[f(0,0,0)]
        for i in r:
            print i

if __name__ == '__main__':
    import profile, pstats

    lineCount = 20
    inpData = ["1",lineCount]#["2","3","1","2 1","1 2 3","4","1","1 2","4 1 2","2 3 1 1"]#
    for i in range(1,lineCount + 1):
        inpData.append(reduce(lambda x, y: x + " " + str(y), range(i), ""))
    strNum = 0
    profile.run('main()', 'result.prof')
    pstats.Stats('result.prof').strip_dirs().sort_stats(-1).print_stats()