Wstęp do programowania w C++

Soczystość

Jabłka przemieszczają się po taśmociągu jeden za drugim, a Jasiu musi wybrać spośród wszystkich jabłek te, których suma soczystości będzie możliwie największa. To jest jego zadanie. Ponieważ jabłka przemieszczają się bardzo szybko, Jasiu nie zdąży wybrać dwóch kolejnych jabłek, dlatego musi sobie zaplanować przed rozpoczęciem pracy, które jabłka będzie wybierał. Znając z góry ciąg soczystości kolejnych jabłek na taśmociągu, napisz program, który wyznaczy największą sumę sozystości, jaką można uzyskać z jabłek na taśmociągu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego w pierwszym wierszu podana jest liczba n (1 ≤ n ≤ 10⁵) oznaczająca liczbę jabłek na taśmociągu. W wierszu drugim, danych jest n liczb całkowitych a_i (1 ≤ a_i ≤ 10⁴) oznaczających soczystości kolejnych jabłek.
Wyjście
Dla każdego przypadku testowego należy podać maksymalną sumę soczystości.

Przykład

Wejście
2
7
2 4 6 8 3 5 9
5
2 2 2 2 2

Wyjście
21
6