编程题：数塔

数塔如图所示，若每一步只能走到相邻的结点（图中有数字的方格），则从最顶层走到最底层所经过的所有结点的数字之和最大是多少？测试数据保证结果处于int范围内。



### 输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入一个整数n(1≤n≤100)，表示数塔的高度，接下来输入n行表示数塔的数字，其中第i行有i个整数。

### 输出格式:

对于每组测试，输出一行，包含一个整数，表示从最顶层走到最底层可能得到的最大和。

### 输入样例:

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



### 输出样例:

out
32



### 出处:
HDOJ 2084






答案：若无答案欢迎评论