import psyco
psyco.full()

def main():
	casesCount=input()
	for caseNum in range(casesCount):
		rowCount=input()
		triangle=[]
		for i in range(rowCount):
			triangle+=[[int(x) for x in raw_input().split()]]
		for i in range(rowCount - 2, -1, -1):
			for j in range(i+1):
				triangle[i][j]+= triangle[i+1][j] > triangle[i+1][j+1] and triangle[i+1][j] or triangle[i+1][j+1]
		print rowCount == 0 and '0' or triangle[0][0]

main()

import psyco
psyco.full()

def solve():
    global rc,rvrc,triangle,rowCount,results
    casesCount=1000
    results=[]
    for caseNum in range(casesCount):
        for i in range(rowCount - 2, -1, -1):
            for j in range(i+1):
                triangle[i][j]+= triangle[i+1][j] > triangle[i+1][j+1] and triangle[i+1][j] or triangle[i+1][j+1]
        results+=[rowCount == 0 and '0' or triangle[0][0]]
    print results[0]
    for i in results:
        None#print i

# profile
def generateT(n):
    t=[]
    for i in range(n):
        t.append(range(1, i+2))
    return t

def main():
	from datetime import datetime
	global rc,rvrc,triangle,rowCount,results
	rowCount = 100
	triangle=generateT(rowCount)

	t = datetime.now()
	solve()
	print datetime.now() - t

if __name__ == '__main__':
	main()

 triangle+=[[int(x) for x in raw_input().split()]]