def main():
	global rc,rvrc,triangle,rowCount,results
	casesCount=100
	results=[]
	rc = range(500000)
	rvrc = rc[:]
	rvrc.reverse()
	for caseNum in rc[:casesCount]:
		if rowCount>0:
			for i in rvrc[1-rowCount:]:
				for j in rc[: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+=[triangle[0][0]]
		else:
			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


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

    rowCount = 100
    triangle=generateT(rowCount)
    profile.run('main()', 'result.prof')
    pstats.Stats('result.prof').strip_dirs().sort_stats(-1).print_stats()

casesCount=input()
results=[]
rc = range(500000)
rvrc = rc[:]
rvrc.reverse()
for caseNum in rc[:casesCount]:
	rowCount=input()
	triangle=[]
	for i in rc[:rowCount]:
		triangle+=[map(int,raw_input().split())]
	if rowCount>0:
		for i in rvrc[1-rowCount:]:
			for j in rc[: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+=[triangle[0][0]]
	else:
		results += [0]
for i in results:
	print i

        for i in rvrc[1-rowCount:]:
            for j in rc[: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]

			for i in rvrc[1-rowCount:]:
				triangle[i] = [triangle[i][j] + (triangle[i+1][j] > triangle[i+1][j+1] and triangle[i+1][j] or triangle[i+1][j+1]) for j in rc[:i+1]]

import psyco
psyco.full()