7 
3 8 

8 1 0 

2 7 4 4 

4 5 2 6 5 

(圖一) 

圖一表示一個5行的數(shù)字三角形。假設(shè)給定一個n行數(shù)字三角形,計(jì)算出從三角形頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。 
每一步只能由當(dāng)前位置向左下或右下。

你的程序要能接受標(biāo)準(zhǔn)輸入。第一行包含一個整數(shù)T，表示總的測試次數(shù)。 
對于每一種情況：第一行包含一個整數(shù)N,其中1 < N < 100,表示三角形的行數(shù)。 
接下來的N行輸入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。

輸出每次測試的最大值并且占一行。

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

30