Эта специальная игровая доска состоит из $n$ клеток, где клетка $i$ ($3 \le i \le n$) имеет положительное целочисленное значение $a_i$.

Вы решили сыграть партию со своим напарником. В начале игры вы занимаете клетку $1$ и ставите на неё свою фишку, а ваш напарник занимает клетку $2$ и ставите на неё свою фишку. В этот момент заняты только эти две клетки. Начальные очки обоих игроков равны нулю.

Вы ходите первым, после чего игроки ходят по очереди. При каждом ходе, если фишка текущего игрока находится в клетке $x$, игрок обязан выбрать шаг $d \in \{1, 2, 3, 4\}$, такой что $x + d \le n$ и клетка $x + d$ еще не занята. Затем игрок прибавляет к своему счёту значение $a_{x+d}$ этой клетки и перемещает свою фишку в клетку $x + d$. После завершения прыжка игрок навсегда занимает эту новую клетку. В частности, если не существует ни одного допустимого шага, игрок пропускает ход. Игра заканчивается, когда ни один из игроков не может сделать ход.

Очевидно, что вы и ваш напарник достаточно умны и в процессе игры придерживаетесь оптимальной стратегии. Чтобы заранее предсказать результат игры, вам нужно вычислить разность между вашим итоговым счётом и итоговым счётом вашего напарника.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $T$ ($1 \le T \le 10^3$), количество наборов данных. Для каждого набора данных:

• Первая строка содержит целое число $n$ ($6 \le n \le 10^5$), количество клеток на доске.
• Вторая строка содержит $n - 2$ целых числа $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$), представляющих значения каждой клетки.

Гарантируется, что сумма $n$ по всем наборам данных не превышает $10^5$.

Выходные данные

Для каждого набора данных выведите одну строку с целым числом, представляющим разность между вашим итоговым счётом и итоговым счётом вашего напарника.

Примеры

Входные данные 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

Выходные данные 1

5
0
-7
8
90
1000000000

Примечание

Ниже для представления результата игры используется строка длины $n$, где символ . означает, что клетка никем не занята, символ O означает, что клетка занята вами, а символ X означает, что клетка занята вашим напарником.

Для первого набора данных при первом ходе у вас есть три варианта: Выбрать шаг $d = 2$, прыгнуть в клетку $3$, тогда результат игры будет OXOXXO, разность очков $-6$; Выбрать шаг $d = 3$, прыгнуть в клетку $4$, тогда результат игры будет OX.OOX, разность очков $5$; * Выбрать шаг $d = 4$, прыгнуть в клетку $5$, тогда результат игры будет OX..OX, разность очков $-1$.

Таким образом, результат игры OX.OOX, разность очков $5$.

Для второго набора данных один из возможных результатов игры — OXOXOXOX, разность очков $0$.

Для третьего набора данных один из возможных результатов игры — OX..OXOOOX, разность очков $-7$.

Для четвертого набора данных один из возможных результатов игры — OX..OXXXO, разность очков $8$.

Для пятого набора данных один из возможных результатов игры — OXXXOXOO, разность очков $90$.

Для шестого набора данных один из возможных результатов игры — OX..OXO.XO, разность очков $1000000000$.

Входные данные 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

Выходные данные 2

5
13
8
3
9
9