Ta specjalna plansza składa się z $n$ pól, gdzie pole $i$ ($3 \le i \le n$) ma wartość punktową będącą liczbą całkowitą dodatnią $a_i$.

Postanowiłeś rozegrać partię ze swoim współzawodnikiem. Na początku gry zajmujesz pole 1, na którym kładziesz swój pionek, a Twój współzawodnik zajmuje pole 2, na którym kładzie swój pionek. W tym momencie tylko te dwa pola są zajęte. Początkowe wyniki obu graczy wynoszą zero.

Grę rozpoczynasz Ty, a następnie gracze wykonują ruchy na zmianę. W każdym ruchu, jeśli pionek aktualnie ruszającego się gracza znajduje się na polu $x$, gracz musi wybrać krok $d \in \{1, 2, 3, 4\}$, spełniający warunek $x + d \le n$, przy czym pole $x + d$ nie może być jeszcze zajęte. Następnie gracz dodaje do swojego wyniku wartość punktową tego pola $a_{x+d}$ i przesuwa swój pionek na pole $x + d$. Po wykonaniu skoku gracz zajmuje to nowe pole na stałe. W szczególności, jeśli nie istnieje żaden legalny krok, gracz nie może wykonać ruchu w tej turze i pomija ją. Gra kończy się, gdy żaden z graczy nie może wykonać ruchu.

Oczywiście, zarówno Ty, jak i Twój współzawodnik jesteście wystarczająco bystrzy i w trakcie gry będziecie stosować optymalne strategie. Aby przewidzieć wynik rozgrywki, musisz obliczyć wartość Twojego całkowitego wyniku pomniejszonego o całkowity wynik Twojego współzawodnika po zakończeniu gry.

Wejście

Każdy zestaw testowy zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^3$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

• Pierwsza linia zawiera liczbę całkowitą $n$ ($6 \le n \le 10^5$), oznaczającą liczbę pól na planszy.

• Druga linia zawiera $n - 2$ liczb całkowitych $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$), oznaczających wartości punktowe poszczególnych pól.

Suma $n$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wyprowadź w jednej linii liczbę całkowitą oznaczającą różnicę między Twoim całkowitym wynikiem a całkowitym wynikiem Twojego współzawodnika.

Przykład

Wejście 1

6
6
1 6 3 4
10
1 1 1 1 1 1 1 1
10
1 1 1 1 1 1 1 10
9
1 1 1 1 1 1 10
8
10 1 1 1 1 100
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1

Wyjście 1

5
0
-7
8
90
1000000000

Uwagi

Poniżej użyto ciągu znaków o długości $n$ do przedstawienia wyniku gry, gdzie znak . oznacza, że pole nie zostało przez nikogo zajęte, znak O oznacza, że pole zostało zajęte przez Ciebie, a znak X oznacza, że pole zostało zajęte przez Twojego współzawodnika.

Dla pierwszego przypadku testowego, w pierwszym ruchu masz trzy możliwości:

• Wybór kroku $d = 2$, skok na pole 3, wynik gry to OXOXXO, różnica punktowa wynosi $-6$;
• Wybór kroku $d = 3$, skok na pole 4, wynik gry to OX.OOX, różnica punktowa wynosi $5$;
• Wybór kroku $d = 4$, skok na pole 5, wynik gry to OX..OX, różnica punktowa wynosi $-1$.

Zatem wynik gry to OX.OOX, a różnica punktowa wynosi $5$.

Dla drugiego przypadku testowego, jednym z możliwych wyników gry jest OXOXOXOX, różnica punktowa wynosi $0$.

Dla trzeciego przypadku testowego, jednym z możliwych wyników gry jest OX..OXOOOX, różnica punktowa wynosi $-7$.

Dla czwartego przypadku testowego, jednym z możliwych wyników gry jest OX..OXXXO, różnica punktowa wynosi $8$.

Dla piątego przypadku testowego, jednym z możliwych wyników gry jest OXXXOXOO, różnica punktowa wynosi $90$.

Dla szóstego przypadku testowego, jednym z możliwych wyników gry jest OX..OXO.XO, różnica punktowa wynosi $1000000000$.

Wejście 2

6
9
7 6 2 2 5 8 7
10
8 26 18 1 11 9 15 9
11
8 3 9 2 3 4 8 8 7
12
5 6 5 3 1 2 1 1 5 4
15
6 6 7 2 2 2 5 2 2 4 7 7 7
18
7 4 5 1 2 6 7 5 7 3 7 3 6 5 6 6

Wyjście 2

5
13
8
3
9
9