Shortening codes

Wyobraź sobie trójkąt liczb, w którym w pierwszej linii znajduje się jedna liczba, w drugiej dwie itd. Napisz program, który obliczy największą sumę liczb, które pojawiają się na ścieżce zaczynającej się w pierwszej linii, a kończącej w ostatniej. Każdy kolejny element ścieżki znajduje się rząd niżej (nie można iść w bok, ani do góry), ale tylko bezpośrednio poniżej lub jedno miejsce w prawo od miejsca ostatniej w danym momencie liczby w ścieżce. Liczba wierszy jest dodatnia i mniejsza od 101, a wszystkie liczby w trójkącie są z przedziału <0;1002>.

Wejście

W pierwszym teście znajduje się liczba testów n (n<101). Każdy z testów zaczyna się wysokością trójkąta h, po której następuje h wierszy. Kolejne wiersze mają natomiast długość od 1 do h.

Wyjście

Największa suma liczb leżących na wybranej ścieżce.

Przykład

Wejście:
2
3
1
2 1
1 2 3
4 
1 
1 2 
4 1 2
2 3 1 1 

Wyjście:
5
9