Migrated from Lutece 1011 数字三角形

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

Input

多组测试数据，第一行为数据组数T，每组测试数据的第一行是一个整数$n (1 < n \leq 100)$，给出三角形的行数。下面的$n$ 行给出数字三角形。数字三角形上的数的范围都在$0$ 和$100$ 之间。

Output

输出每组输入数据的最大和，占一行。

Samples

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

30

Resources

POJ