This problem is a programming version of Problem 67 from projecteuler.net
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is . The path is denoted by numbers in bold.
That is, .
Find the maximum total from top to bottom of the triangle given in input.
Input Format
First line contains , the number of testcases. For each testcase:
First line contains , the number of rows in the triangle.
For next lines, 'th line contains numbers.
Constraints
Each element of triangle lies between and (both inclusive).
Output Format
Print the required answer for each testcase on a new line.
Sample Input
2
4
3
7 4
2 4 6
8 5 9 3
4
3
7 4
2 4 6
8 5 9 3
Sample Output
23
23