HZNUOJ

三角形

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:108     AC:69     Score:96.67

Description

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

(图一)

图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径,使该路径经过的数字总和最大。每一步只能由当前位置向左下或右下。

Input

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

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

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

Output

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

Samples

input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
output
30