_{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
```