题目：三角形路径最大和

欧拉 第 18 题。

在一个给定的数字三角形中，从顶部开始，每次可以移动到下一行中与当前位置 相邻的数字。 你的任务是在给定的三角形中，找到从顶部到底部的 最大路径和。

例如，以下三角形：

   3
  7 4
 2 4 6
8 5 9 3

其最大路径为：

3 → 7 → 4 → 9 = 23

输入格式

• 第一行包含一个整数 T，表示测试用例数量。

• 对于每个测试用例：

  • 第一行包含整数 N，表示三角形的行数。
  • 接下来 N 行，第 i 行包含 i 个整数，表示三角形的第 i 行。

输出格式

对于每个测试用例，输出一个整数，表示该三角形从顶部到底部的最大路径和。

数据范围

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 15
• 每个数字的取值范围为 [0, 100]

样例输入

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

样例输出

23

样例说明

如题目描述中所示，最大路径和为 23。