Given an integer N, let us consider a triangle of numbers of N lines in which a number a_{11} appears in the first line, two numbers a_{21} and a_{22} appear in the second line, three numbers a_{31}, a_{32} and a_{33} appear in the third line, etc. In general, i numbers a_{i1}, a_{i2} \dots a_{ii} appear in the i^{th} line for all 1 ≤ i ≤ N. Develop a program that will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:
on each path the next number is located on the row below, more precisely either directly below or below and one place to the right.

Warning: large Input/Output data, be careful with certain languages 

------ Input Format ------ 

- The first line of the input contains an integer T, the number of test cases. 
- Then T test cases follow. Each test case starts with an integer N, the number of rows. Then N lines follow where in i^{th} line contains i integers a_{i1}, a_{i2} \dots a_{ii}.

------ Output Format ------ 

For each test case print the maximum path sum in a separate line.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N < 100$
$0 ≤ a_{ij} < 100$

----- Sample Input 1 ------ 
2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1

----- Sample Output 1 ------ 
5
9
----- explanation 1 ------ 
Test case 1:

There are a total of $4$ paths
- $(1,1) \rightarrow (2, 1) \rightarrow (3, 1)$ with sum equal to $4$.
- $(1,1) \rightarrow (2, 1) \rightarrow (3, 2)$ with sum equal to $5$.
- $(1,1) \rightarrow (2, 2) \rightarrow (3, 2)$ with sum equal to $4$.
- $(1,1) \rightarrow (2, 2) \rightarrow (3, 3)$ with sum equal to $5$.

Therefore, the maximum sum over all paths is equal to $5$.

Test case 2:

There are a total of $8$ paths
- $(1,1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (4, 1)$ with sum equal to $8$.
- $(1,1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (4, 2)$ with sum equal to $9$.
- $(1,1) \rightarrow (2, 1) \rightarrow (3, 2) \rightarrow (4, 2)$ with sum equal to $7$.
- $(1,1) \rightarrow (2, 1) \rightarrow (3, 2) \rightarrow (4, 3)$ with sum equal to $4$.
- $(1,1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (4, 2)$ with sum equal to $7$.
- $(1,1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (4, 3)$ with sum equal to $5$.
- $(1,1) \rightarrow (2, 2) \rightarrow (3, 3) \rightarrow (4, 3)$ with sum equal to $6$.
- $(1,1) \rightarrow (2, 2) \rightarrow (3, 3) \rightarrow (4, 4)$ with sum equal to $6$.

Therefore, the maximum sum over all paths is equal to $9$.

Source: codechef | Difficulty: EASY
Tags: Dynamic programming


Solutions:
x = int(input())
for i in range(x):
	y = int(input())
	l = []
	for j in range(y):
		p = list(map(int, input().split()))
		l.append(p)
	a = y
	for _ in range(y - 1, -1, -1):
		for k in range(0, _):
			l[_ - 1][k] += max(l[_][k], l[_][k + 1])
	print(l[0][0])


T = int(input())
res = []
for i in range(T):
	arr = []
	N = int(input())
	for x in range(N):
		arr.append([int(i) for i in input().split()])
	for i in reversed(range(len(arr) - 1)):
		for j in range(i + 1):
			arr[i][j] += max(arr[i + 1][j], arr[i + 1][j + 1])
	res.append(arr[0][0])
for x in res:
	print(x)


for _ in range(int(input())):
	n = int(input())
	li = list()
	for i in range(n):
		li.append(list(map(int, input().split())))
	for i in range(1, n):
		li[i][0] += li[i - 1][0]
	for i in range(1, n):
		for j in range(1, i + 1):
			if j == i:
				li[i][j] += li[i - 1][j - 1]
			else:
				li[i][j] = li[i][j] + max(li[i - 1][j], li[i - 1][j - 1])
	print(max(li[-1]))


t = int(input())
for _ in range(t):
	l = []
	m = int(input())
	for j in range(m):
		n = list(map(int, input().split()))
		l.append(n)
	for j in range(m - 2, -1, -1):
		for k in range(0, j + 1):
			l[j][k] += max(l[j + 1][k], l[j + 1][k + 1])
	print(l[0][0])


def max_path_sum(triangle):
	n = len(triangle)
	for i in range(n - 2, -1, -1):
		for j in range(i + 1):
			triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1])
	return triangle[0][0]
t = int(input())
for _ in range(t):
	n = int(input())
	triangle = []
	for i in range(n):
		row = list(map(int, input().split()))
		triangle.append(row)
	print(max_path_sum(triangle))


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		row = list(map(int, input().split()))
		a.append(row)
	dp = [[0] * n for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(i + 1):
			if i == n - 1:
				dp[i][j] = a[i][j]
			else:
				dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1])
	print(dp[0][0])


def array_safe_get(arr, i):
	if 0 <= i < len(arr):
		return arr[i]
	return 0

def handle(lines):
	c = [0]
	for line in lines:
		c = [max(array_safe_get(c, index) + element, array_safe_get(c, index - 1) + element) for (index, element) in enumerate(line)]
	return max(c)
t = int(input())
for _ in range(t):
	n = int(input())
	sums = []
	lines = [list(map(int, input().split())) for i in range(n)]
	print(handle(lines))


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	for y in range(n - 2, -1, -1):
		for x in range(y + 1):
			a[y][x] = a[y][x] + max(a[y + 1][x], a[y + 1][x + 1])
	print(a[0][0])


for _ in range(int(input())):
	n = int(input())
	c = []
	a = []
	for i in range(n):
		c.append([0] * n)
		a.append([0] * n)
	for i in range(n):
		x = input().split()
		for j in range(i + 1):
			a[i][j] = int(x[j])
	c[0][0] = a[0][0]
	for i in range(1, n):
		c[i][0] = c[i - 1][0] + a[i][0]
	for i in range(1, n):
		for j in range(1, i + 1):
			c[i][j] = max(c[i - 1][j], c[i - 1][j - 1]) + a[i][j]
	print(max(c[n - 1]))


t = int(input())
for _ in range(t):
	n = int(input())
	l = [list(map(int, input().split())) for i in range(n)]
	table = [[0 for j in range(i + 1)] for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(i, -1, -1):
			if i == n - 1:
				table[i][j] = l[i][j]
			else:
				table[i][j] = max(l[i][j] + table[i + 1][j], l[i][j] + table[i + 1][j + 1])
	print(table[0][0])


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	k = [[0 for i in range(n)] for j in range(1, n + 1)]
	k[0][0] = l[0][0]
	for i in range(1, n):
		k[i][0] = k[i - 1][0] + l[i][0]
	for i in range(1, n):
		for j in range(1, i + 1):
			k[i][j] = l[i][j] + max(k[i - 1][j], k[i - 1][j - 1])
	print(max(k[-1]))


t = int(input())
for i in range(t):
	n = int(input())
	triangle = []
	max_sum = []
	for j in range(n):
		row = list(map(int, input().split()))
		triangle.append(row)
		max_sum.append([0] * len(row))
	for j in range(n):
		for k in range(j + 1):
			if j == 0:
				max_sum[j][k] = triangle[j][k]
			elif k == 0:
				max_sum[j][k] = max_sum[j - 1][k] + triangle[j][k]
			elif k == j:
				max_sum[j][k] = max_sum[j - 1][k - 1] + triangle[j][k]
			else:
				max_sum[j][k] = max(max_sum[j - 1][k - 1], max_sum[j - 1][k]) + triangle[j][k]
	print(max(max_sum[n - 1]))


def ans(arr, N):
	while N:
		for i in range(N):
			arr[N - 1][i] += max(arr[N][i], arr[N][i + 1])
		N -= 1
	return arr[0][0]
T = int(input())
for i in range(T):
	N = int(input())
	arr = []
	for i in range(N):
		item = list(map(int, input().split()))
		arr.append(item)
	print(ans(arr, N - 1))


T = int(input())
for _ in range(T):
	N = int(input())
	l = []
	for j in range(N):
		Arr = list(map(int, input().split()))
		l.append(Arr)
	for j in range(N - 2, -1, -1):
		for k in range(0, j + 1):
			l[j][k] += max(l[j + 1][k], l[j + 1][k + 1])
	print(l[0][0])


EP = int(input())
for i in range(EP):
	ep = []
	pc = int(input())
	for j in range(pc):
		epc = list(map(int, input().split()))
		ep.append(epc)
	for j in range(pc - 2, -1, -1):
		for k in range(0, j + 1):
			ep[j][k] += max(ep[j + 1][k], ep[j + 1][k + 1])
	print(ep[0][0])


def max_path_sum(n, arr):
	dp = [[0] * n for _ in range(n)]
	dp[0][0] = arr[0][0]
	for i in range(1, n):
		for j in range(i + 1):
			if j == 0:
				dp[i][j] = dp[i - 1][j] + arr[i][j]
			elif j == i:
				dp[i][j] = dp[i - 1][j - 1] + arr[i][j]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j]
	return max(dp[n - 1])
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	print(max_path_sum(n, arr))


for _ in range(int(input())):
	n = int(input())
	k = []
	for j in range(n):
		a = list(map(int, input().split()))
		k.append(a)
	for i in range(n - 2, -1, -1):
		for o in range(i + 1):
			k[i][o] += max(k[i + 1][o], k[i + 1][o + 1])
	print(k[0][0])


t = int(input())
for i in range(t):
	l = []
	a = int(input())
	for j in range(a):
		b = list(map(int, input().split()))
		l.append(b)
	for j in range(a - 2, -1, -1):
		for k in range(0, j + 1):
			l[j][k] += max(l[j + 1][k], l[j + 1][k + 1])
	print(l[0][0])


def solve():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = []
		for j in range(n):
			a.append(list(map(int, input().split())))
		dp = [[0 for j in range(n)] for i in range(n)]
		dp[0][0] = a[0][0]
		for i in range(1, n):
			for j in range(i + 1):
				if j == 0:
					dp[i][j] = dp[i - 1][j] + a[i][j]
				elif j == i:
					dp[i][j] = dp[i - 1][j - 1] + a[i][j]
				else:
					dp[i][j] = a[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])
		ans = -1000000000
		for i in range(n):
			ans = max(ans, dp[n - 1][i])
		print(ans)
solve()


def f(a, i, j, dp):
	if i == len(a) - 1:
		return a[i][j]
	if dp[i][j] != -1:
		return dp[i][j]
	down = a[i][j] + f(a, i + 1, j, dp)
	diag = a[i][j] + f(a, i + 1, j + 1, dp)
	maxPathSum = max(down, diag)
	dp[i][j] = maxPathSum
	return maxPathSum
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	bigList = []
	dp = []
	while N > 0:
		N -= 1
		bigList.append(list(map(int, input().split())))
	dp = [[-1 for col in row] for row in bigList]
	print(f(bigList, 0, 0, dp))


def fun(arr):
	new = [[1 for j in range(len(i))] for i in arr]
	new[-1] = [i for i in arr[-1]]
	for i in range(len(arr) - 2, -1, -1):
		for j in range(len(arr[i])):
			new[i][j] = arr[i][j] + max(new[i + 1][j], new[i + 1][j + 1])
	return new[0][0]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [list(map(int, input().split())) for _ in range(n)]
	print(fun(arr))


def maximum_sum(triangle, N):
	dp = [0 for i in range(N)]
	max_sum = 0
	for i in range(0, N):
		for j in range(i, -1, -1):
			dp[j] = max(dp[j], 0 if j == 0 else dp[j - 1]) + triangle[i][j]
			max_sum = max(dp[j], max_sum)
	return max(dp)
T = int(input())
for _ in range(T):
	N = int(input())
	triangle = []
	dp = [[0 for i in range(N * (N - 1) // 2)] for j in range(N)]
	for times in range(N):
		triangle.append(list(map(int, input().split())))
	print(maximum_sum(triangle, N))


for i in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		g = list(map(int, input().split()))
		a.append(g)
	ma = 0
	for j in range(n - 2, -1, -1):
		for k in range(j + 1):
			a[j][k] += max(a[j + 1][k], a[j + 1][k + 1])
	print(a[0][0])


def best_path(r, c, n, triangle, memo=None):
	if memo is None:
		memo = {}
	if f'{r}-{c}' in memo:
		return memo[f'{r}-{c}']
	if r == n or c == r + 1:
		memo[f'{r}-{c}'] = 0
		return 0
	ans = triangle[r][c] + max(best_path(r + 1, c, n, triangle, memo), best_path(r + 1, c + 1, n, triangle, memo))
	memo[f'{r}-{c}'] = ans
	return ans
t = int(input())
for _ in range(t):
	triangle = []
	n = int(input())
	for i in range(n):
		vals = list(map(int, input().split()))
		triangle.append(vals)
	print(best_path(0, 0, n, triangle))


t = int(input())
for i in range(t):
	n = int(input())
	x = []
	for j in range(n):
		a = list(map(int, input().split()))
		x.append(a)
	for _ in range(n - 2, -1, -1):
		for __ in range(_ + 1):
			x[_][__] += max(x[_ + 1][__], x[_ + 1][__ + 1])
	print(x[0][0])


class Solution:

	def solve(self, matrix, rows, cols):
		prev_row = matrix[0]
		next_row = []
		for row in range(1, rows):
			next_row = matrix[row][:]
			for (key, value) in enumerate(prev_row):
				next_row[key] = max(next_row[key], matrix[row][key] + value)
				next_row[key + 1] = max(next_row[key + 1], matrix[row][key + 1] + value)
			prev_row = next_row[:]
		return max(prev_row)

class Driver:

	def __init__(self):
		self._solver = Solution()

	def drive(self):
		test_cases = int(input().strip())
		for _ in range(test_cases):
			rows = int(input().strip())
			matrix = []
			for row in range(rows):
				array = list(map(int, input().strip().split(' ')))
				matrix.append(array)
			ans = self._solver.solve(matrix, rows, rows)
			print(ans)
Driver().drive()


t = int(input())
for _ in range(t):
	n = int(input())
	lst = []
	for j in range(n):
		a = [int(j) for j in input().split()]
		lst.append(a)
	for i in range(n - 1, -1, -1):
		for j in range(0, i):
			if lst[i][j] <= lst[i][j + 1]:
				lst[i - 1][j] = lst[i - 1][j] + lst[i][j + 1]
			else:
				lst[i - 1][j] = lst[i - 1][j] + lst[i][j]
	print(lst[0][0])


def sumintri(arr, n):
	for i in range(n - 1, -1, -1):
		for j in range(i):
			if arr[i][j] > arr[i][j + 1]:
				arr[i - 1][j] += arr[i][j]
			else:
				arr[i - 1][j] += arr[i][j + 1]
	return arr[0][0]
for _ in range(int(input())):
	n = int(input())
	l = []
	for x in range(n):
		t = list(map(int, input().split()))
		l.append(t)
	print(sumintri(l, n))


def dp(triangle):
	n = len(triangle)
	table = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	table[0][0] = triangle[0][0]
	for i in range(1, n):
		for j in range(i + 1):
			if j == 0:
				table[i][j] = table[i - 1][j] + triangle[i][j]
			elif j == i:
				table[i][j] = table[i - 1][j - 1] + triangle[i][j]
			else:
				table[i][j] = max(table[i - 1][j - 1], table[i - 1][j]) + triangle[i][j]
	return max(table[n - 1])
for _ in range(int(input())):
	triangle = []
	for i in range(int(input())):
		triangle.append(list(map(int, input().strip().split())))
	print(dp(triangle))


for t in range(int(input())):
	n = int(input())
	l = []
	for i in range(1, n + 1):
		a = []
		a = [int(i) for i in input().split()]
		l.append(a)
	i = n - 1
	k = 1
	while i > 0:
		for j in range(n - k):
			m = max(l[i][j], l[i][j + 1])
			l[i - 1][j] = l[i - 1][j] + m
		i = i - 1
		k = k + 1
	print(l[0][0])


T = int(input())
for _ in range(T):
	N = int(input())
	A = []
	for x in range(N):
		a = list(map(int, input().split()))
		A.append(a)
	for x in range(N - 2, -1, -1):
		for y in range(0, x + 1):
			A[x][y] = A[x][y] + max(A[x + 1][y], A[x + 1][y + 1])
	print(A[0][0])


def solve(i, j):
	if i == n - 1:
		return grid[i][j]
	if j >= len(grid[i]):
		return -1
	if dp[i][j] == -1:
		dp[i][j] = grid[i][j] + max(solve(i + 1, j), solve(i + 1, j + 1))
	return dp[i][j]
t = int(input())
for _ in range(t):
	n = int(input())
	dp = []
	grid = []
	for i in range(n):
		row = list(map(int, input().split(' ')))
		grid.append(row)
		dp.append([-1] * (i + 1))
	print(solve(0, 0))


t = int(input())
for i in range(t):
	n = int(input())
	arr = []
	for x in range(n):
		a = [int(x) for x in input().split()]
		arr.append(a)
	for x in range(n - 2, -1, -1):
		for y in range(0, x + 1):
			arr[x][y] = arr[x][y] + max(arr[x + 1][y], arr[x + 1][y + 1])
	print(arr[0][0])


t = int(input())
while t:
	n = int(input())
	a = []
	for i in range(n):
		arr = list(map(int, input().split()))
		a.append(arr)
	for i in range(n - 1, -1, -1):
		for j in range(i):
			a[i - 1][j] += max(a[i][j + 1], a[i][j])
	print(a[0][0])
	t -= 1


n = int(input())
for i in range(n):
	n1 = int(input())
	dp = []
	for i in range(n1):
		dp.append(list(map(int, input().split(' '))))
	for i in range(1, n1):
		for j in range(i + 1):
			if j == 0:
				dp[i][j] = dp[i - 1][j] + dp[i][j]
			elif j == i:
				dp[i][j] = dp[i - 1][j - 1] + dp[i][j]
			else:
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + dp[i][j]
	print(max(dp[-1]))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().strip().split())))
	for i in range(1, n):
		arr[i][0] = arr[i][0] + arr[i - 1][0]
		arr[i][-1] = arr[i][-1] + arr[i - 1][-1]
		for j in range(1, i):
			arr[i][j] = arr[i][j] + max(arr[i - 1][j], arr[i - 1][j - 1])
	print(max(arr[-1]))


for i in range(int(input())):
	n = int(input())
	l = [[int(j) for j in input().split()] for i in range(n)]
	dp = [[0 for i in range(j + 1)] for j in range(n)]
	dp[0][0] = l[0][0]
	for i in range(1, n):
		for j in range(i + 1):
			if j == 0:
				dp[i][j] = dp[i - 1][j] + l[i][j]
			elif i == j:
				dp[i][j] = dp[i - 1][j - 1] + l[i][j]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + l[i][j]
	m = 0
	for i in range(n):
		if dp[n - 1][i] > m:
			m = dp[n - 1][i]
	print(m)


t = int(input())

def answer(a, b, lookup, x):
	lookup[0][0] = x[0][0]
	if a == 1:
		lookup[1][b] = x[1][b] + x[0][0]
	if lookup[a][b] == None:
		if b == 0:
			lookup[a][0] = x[a][0] + answer(a - 1, 0, lookup, x)
		else:
			if b == len(lookup[a]) - 1:
				ddd = answer(a - 1, b - 1, lookup, x)
			else:
				ddd = max(answer(a - 1, b, lookup, x), answer(a - 1, b - 1, lookup, x))
			lookup[a][b] = x[a][b] + ddd
	return lookup[a][b]
for i in range(t):
	n = int(input())
	lookup = [[None for i in range(j + 1)] for j in range(n)]
	x = []
	y = []
	for i in range(n):
		x.append(list(map(int, input().split())))
	for yay in range(n):
		y.append(answer(n - 1, yay, lookup, x))
	print(max(y))


for i in range(int(input())):
	c = []
	for i in range(int(input())):
		c.append([*map(int, input().split())])
	for x in range(len(c) - 2, -1, -1):
		for y in range(x + 1):
			c[x][y] += max(c[x + 1][y], c[x + 1][y + 1])
	print(c[0][0])


def maxTri(i, j, dp):
	if (i, j) in dp:
		return dp[i, j]
	if i >= n or j >= n:
		return 0
	dp[i, j] = max(l[i][j] + maxTri(i + 1, j, dp), l[i][j] + maxTri(i + 1, j + 1, dp))
	return dp[i, j]
t = int(input())
for _ in range(t):
	n = int(input())
	l = [list(map(int, input().split())) for i in range(n)]
	dp = {}
	print(maxTri(0, 0, dp))


T = int(input())
for _ in range(T):
	N = int(input())
	lst = []
	for i in range(N):
		temp = [int(i) for i in input().split()]
		lst.append(temp)
	for i in range(N - 1, -1, -1):
		for j in range(0, i):
			if lst[i][j] >= lst[i][j + 1]:
				lst[i - 1][j] = lst[i - 1][j] + lst[i][j]
			else:
				lst[i - 1][j] = lst[i - 1][j] + lst[i][j + 1]
	print(lst[0][0])


t = int(input())
for i in range(t):
	n = int(input())
	m = []
	for i in range(n):
		a = list(map(int, input().split()))
		m.append(a)
	k = n - 2
	for j in range(k, -1, -1):
		for i in range(len(m[j])):
			m[j][i] += max(m[j + 1][i], m[j + 1][i + 1])
	print(m[0][0])


import sys

def dp_max_sum(row, col, n, triangle, cache):
	if cache[row][col] is not None:
		return cache[row][col]
	elif row == n - 1:
		return triangle[row][col]
	else:
		down = dp_max_sum(row + 1, col, n, triangle, cache)
		down_right = dp_max_sum(row + 1, col + 1, n, triangle, cache)
		cache[row][col] = triangle[row][col] + max(down, down_right)
		return cache[row][col]
test = int(input())
while test:
	n = int(sys.stdin.readline().rstrip('\n'))
	triangle = []
	for _ in range(n):
		line = [int(x) for x in sys.stdin.readline().rstrip('\n').split()]
		triangle.append(line)
	cache = [[None] * n for _ in range(n)]
	print(dp_max_sum(0, 0, n, triangle, cache))
	test -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	triangle = []
	for i in range(n):
		row = list(map(int, input().split()))
		triangle.append(row)
	dp = triangle[-1]
	for i in range(n - 2, -1, -1):
		for j in range(i + 1):
			dp[j] = max(dp[j], dp[j + 1]) + triangle[i][j]
	print(dp[0])


def ijoin(array, char=' '):
	return char.join([str(x) for x in array])

def solve(n, a):
	for y in range(n - 2, -1, -1):
		for x in range(y + 1):
			a[y][x] = a[y][x] + max(a[y + 1][x], a[y + 1][x + 1])
	print(a[0][0])
for t in range(int(input())):
	n = int(input())
	a = [[int(x) for x in input().split()] for _ in range(n)]
	solve(n, a)