三角形

题目描述

7 

3 8 

8 1 0 

2 7 4 4 

4 5 2 6 5 

上述表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。 

每一步只能由当前位置向左下或右下。

输入格式

你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。 

对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。 

接下来的N行输入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。

输出格式

输出每次测试的最大值并且占一行。

样例输入

1 

5 

7 

3 8 

8 1 0  

2 7 4 4 

4 5 2 6 5

样例输出

30