Novice - Problem 5

Pasquale's Tryangle

Elonzo has requested that we help him out by writing a program that can calculate the results of a series of Pasquale's Tryangles. We figured you'd have to have some sort of programming problem to solve in this contest, so why not have you do it!?

A Pasquale's Tryangle starts with a series of 2 or more integer numbers.

The numbers in the row are added from right to left and the partial sum is written beneath each number in that row (forming a new row below). Since the right-most sum is merely the sum of the last number itself, it is not considered a 'true' sum (a true sum should have at least two numbers to add together), and is therefore dropped. These steps are repeated until a row with a single number is arrived at. This final number is referred to as the 'point' of that Pasquale's Tryangle.

As an example, here's a Pasquale's Tryangle of a series of four numbers...

Each number is replaced with the inclusive   1 2 3 4 sum of all numbers to the right of itself...   10 9 7 X ...except for the rightmost number which has no sum   26 16 X   The 'point' of this Pasquale's Tryangle:   42 X

Input: The input will consist of a series of Pasquale's Tryangles to be 'pointed'. Each line of data will contain a single integer number. The first line will be the number of Pasquale's Tryangles to be 'pointed'. The next line will be how many numbers are in the top row of this Tryangle (maximum of 9 numbers). Next will be the numbers that make up the top line of the Tryangle (one number per line). This sequence (number of rows followed by the actual numbers) will be repeated for each of the Tryangles.

Output: For each Pasquale's Tryangle, you are to output a single line with the numeric answer.

Sample Input:

3
4 
1 
2 
3 
4
3 
30 
-5 
-10
6 
1 
1 
1 
1 
1 
1

Sample Output:

42
0
132

Explanation:
First Pasquale's Tryangle is in box above. Here is the second Pasquale's Tryangle:

30   -5  -10
15  -15
0

1   1   1   1   1   1
6   5   4   3   2
20  14  9   5
48  28  14
90  42
132