号碼塔
time limit: 1000/1000 ms (java/others) memory limit: 32768/32768 k (java/others)
total submission(s): 22496 accepted submission(s): 13563
problem description
在講述dp算法的時候，一個經典的樣例就是數塔問題，它是這樣描寫叙述的：
有例如以下所看到的的數塔，要求從頂層走究竟層，若每一步僅僅能走到相鄰的結點，則經過的結點的數字之和最大是多少？
已經告訴你了，這是個dp的題目，你能ac嗎?
input
輸入資料首先包含一個整數c,表示測試執行個體的個數，每一個測試執行個體的第一行是一個整數n(1 <= n <= 100)。表示數塔的高度。接下來用n行數字表示數塔，當中第i行有個i個整數，且全部的整數均在區間[0,99]内。
output
對于每一個測試執行個體，輸出可能得到的最大和，每一個執行個體的輸出占一行。
sample input
sample output