import psyco
psyco.full()
from collections import defaultdict

def main():
    nums = defaultdict(int)
    for x in range(100):
        nums[str(x)] = x
    casesCount=input()
    for caseNum in range(casesCount):
		rowCount=input()
		triangle=[]
		for i in range(rowCount):
			triangle+=[[nums[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()
import sys

rinput = sys.stdin.readline
routput = sys.stdout.write

def main():
    cache = dict([(str(i), i) for i in range(100)])
    for i in range(input()):
        num_of_rows = input()
        prev_line = [cache[rinput().rstrip()]]
        last_line = []
        for j in range(1, num_of_rows):
            last_line = [cache[x] for x in rinput().rstrip().split()]
            for z in range(len(last_line)):
                if z:
                    x = z if z < len(prev_line) else z - 1
                    plx = prev_line[x]
                    last_line[z] += prev_line[z - 1] if prev_line[z - 1] >= plx  else plx
                else:
                    last_line[0] += prev_line[0]
            prev_line = last_line

        routput(str(max(last_line or prev_line)) + '\n')
main()