Este tablero especial consta de $n$ casillas, donde la casilla $i$ ($3 \le i \le n$) tiene un valor entero positivo $a_i$.

Tú decides jugar una partida contra tu compañero de equipo. Al comienzo del juego, tú ocupas la casilla 1 y colocas tu pieza, mientras que tu compañero ocupa la casilla 2 y coloca su pieza; en este momento, solo estas dos casillas están ocupadas. Las puntuaciones iniciales de ambos son cero.

El juego comienza contigo, y luego ambos jugadores se turnan. En cada turno, si la pieza del jugador actual se encuentra en la casilla $x$, el jugador debe elegir un paso $d \in \{1, 2, 3, 4\}$ tal que $x + d \le n$ y la casilla $x + d$ aún no esté ocupada. Luego, el jugador suma el valor de esa casilla $a_{x+d}$ a su propia puntuación y mueve su pieza a la casilla $x + d$. Una vez realizado el salto, el jugador ocupa permanentemente esta nueva casilla. En particular, si no existe ningún paso de salto legal, el jugador no puede realizar ninguna acción en este turno y simplemente pasa su turno. El juego termina cuando ninguno de los dos jugadores puede realizar más movimientos.

Es evidente que tanto tú como tu compañero de equipo son lo suficientemente inteligentes como para adoptar estrategias óptimas durante el juego. Para deducir el resultado de la partida de antemano, necesitas calcular el valor de tu puntuación total menos la puntuación total de tu compañero al finalizar el juego.

Entrada

Cada caso de prueba contiene múltiples conjuntos de datos. La primera línea contiene un entero positivo $T$ ($1 \le T \le 10^3$), que indica el número de conjuntos de datos. Para cada conjunto de datos:

• La primera línea contiene un entero positivo $n$ ($6 \le n \le 10^5$), que indica el número de casillas en el tablero.
• La segunda línea contiene $n - 2$ enteros positivos $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$), que representan los valores de cada casilla respectivamente.

Se garantiza que la suma de $n$ en todos los conjuntos de datos no supera $10^5$.

Salida

Para cada conjunto de datos, imprime una línea con un solo entero, que representa el valor de tu puntuación total menos la puntuación total de tu compañero.

Ejemplos

Entrada 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

Salida 1

5
0
-7
8
90
1000000000

Nota 1

A continuación se utiliza una cadena de longitud $n$ para representar el resultado de la partida, donde el carácter . indica que la casilla no ha sido ocupada por nadie, el carácter O indica que la casilla ha sido ocupada por ti, y el carácter X indica que la casilla ha sido ocupada por tu compañero.

Para el primer conjunto de datos, en el primer turno, tienes las siguientes tres opciones:

• Elegir el paso $d = 2$, saltar a la casilla 3, el resultado de la partida es OXOXXO, la diferencia de puntuación es $-6$.
• Elegir el paso $d = 3$, saltar a la casilla 4, el resultado de la partida es OX.OOX, la diferencia de puntuación es $5$.
• Elegir el paso $d = 4$, saltar a la casilla 5, el resultado de la partida es OX..OX, la diferencia de puntuación es $-1$.

Por lo tanto, el resultado de la partida es OX.OOX, con una diferencia de puntuación de $5$.

Para el segundo conjunto de datos, un posible resultado de la partida es OXOXOXOX, con una diferencia de puntuación de $0$.

Para el tercer conjunto de datos, un posible resultado de la partida es OX..OXOOOX, con una diferencia de puntuación de $-7$.

Para el cuarto conjunto de datos, un posible resultado de la partida es OX..OXXXO, con una diferencia de puntuación de $8$.

Para el quinto conjunto de datos, un posible resultado de la partida es OXXXOXOO, con una diferencia de puntuación de $90$.

Para el sexto conjunto de datos, un posible resultado de la partida es OX..OXO.XO, con una diferencia de puntuación de $1000000000$.

Entrada 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

Salida 2

5
13
8
3
9
9