Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

TRI_SUMS - Sums in a triangle (challenge)

Let us consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:

• on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
• the number of rows is strictly positive, but less than 101;
• all numbers are positive integers between 0 and 1002.

Input

In the first line integer n - the number of test cases (less than 101). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.

Output

For each test case write the determined value in a separate line.

Example

`Input:2312 11 2 34 1 1 2 4 1 22 3 1 1 Output:59`

 Added by: Piotr Kąkol Date: 2010-04-30 Time limit: 5s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS OBJC SCM qobi VB.NET Resource: Copy of Łukasz Kuszner's task SUMITR with different scoring