题目描述

7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5 

如上表示一个 $5$ 行的数字三角形。

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

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

输入格式

你的程序要能接受标准输入。

第一行包含一个整数 $T$ ，表示总的测试次数。

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

接下来的 $N$ 行输入表示三角形的每一行的元素 $A_{i,j}$ 。

输出格式

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

样例输入输出

样例输入

1 
5 
7 
3 8 
8 1 0  
2 7 4 4 
4 5 2 6 5

样例输出

30

数据范围

对于 $100%$ 的数据，保证 $1 < N < 100,0<A_{i,j}<100$ 。