Project Euler #18: Maximum path sum I

_{This problem is a programming version of Problem 18 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

Output Format

For each testcase, print the required answer in a newline.

Sample Input

Sample Output

Explanation

As shown in statement.