Pasquale’s Tryangle

 

Quite possibly one of the most un-famous mathematicians of all time, Pasquale had his own interests. Most of his contemporaries considered him to be a bit eccentric and not completely useful. His great, great grandson is attempting to prove that there are indeed useful applications of his ancestor's research. Recently, Young Elonzo Pasquale discovered an old notebook containing many notes on a mathematical construct described as 'Pasquale's Tryangle'. Elonzo hopes to analyze the results of several of Pasquale's Tryangles in order to figure out what they are good for and to prove that his great, great grandfather was a worthwhile mathematician.

Elonzo has requested that we help him out by writing a program that can calculate the results of a series of Pasquale's Tryangles. A Pasquale 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 Tryangle.

As an example, here's a Pasquale 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

 

...except for the rightmost number which has no sum

 

26

16

 

 

The 'point' of this Pasquale's Tryangle:

 

42

 

 

 

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.

View - Sample Data File