Ce plateau de jeu spécial est composé de $n$ cases, où la case $i$ ($3 \le i \le n$) possède une valeur entière positive $a_i$.

Vous décidez de jouer une partie contre votre coéquipier. Au début du jeu, vous occupez la case 1 et y placez votre pion, tandis que votre coéquipier occupe la case 2 et y place le sien. À ce stade, seules ces deux cases sont occupées. Les scores initiaux des deux joueurs sont nuls.

Le jeu commence par votre tour, puis les deux joueurs jouent à tour de rôle. À chaque tour, si le pion du joueur actif se trouve sur la case $x$, ce joueur doit choisir un pas $d \in \{1, 2, 3, 4\}$ tel que $x + d \le n$ et que la case $x + d$ ne soit pas encore occupée. Le joueur ajoute alors la valeur $a_{x+d}$ de cette case à son score et déplace son pion vers la case $x + d$. Une fois le saut effectué, le joueur occupe définitivement cette nouvelle case. En particulier, s'il n'existe aucun pas de saut légal, le joueur ne peut pas agir ce tour-ci et passe son tour. Le jeu se termine lorsque les deux joueurs ne peuvent plus effectuer d'action.

Étant donné que vous et votre coéquipier êtes tous deux experts en théorie des jeux et jouez de manière optimale, vous devez calculer la différence entre votre score total et celui de votre coéquipier à la fin de la partie.

Entrée

Chaque cas de test contient plusieurs jeux de données. La première ligne contient un entier positif $T$ ($1 \le T \le 10^3$), représentant le nombre de jeux de données. Pour chaque jeu de données : La première ligne contient un entier positif $n$ ($6 \le n \le 10^5$), représentant le nombre de cases sur le plateau. La deuxième ligne contient $n - 2$ entiers positifs $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$), représentant la valeur de chaque case.

La somme des $n$ sur tous les jeux de données ne dépasse pas $10^5$.

Sortie

Pour chaque jeu de données, affichez sur une ligne un entier représentant la valeur de votre score total moins le score total de votre coéquipier.

Exemples

Entrée 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

Sortie 1

5
0
-7
8
90
1000000000

Remarque

Dans ce qui suit, une chaîne de longueur $n$ représente le résultat de la partie, où le caractère . indique que la case n'est occupée par personne, O indique que la case est occupée par vous, et X indique que la case est occupée par votre coéquipier.

Pour la première série de tests, lors de votre première action, vous avez trois choix : Choisir un pas $d=2$, vous déplacez votre pion sur la case 3, le résultat est OXOXXO, la différence de score est $-6$. Choisir un pas $d=3$, vous déplacez votre pion sur la case 4, le résultat est OX.OOX, la différence de score est $5$. * Choisir un pas $d=4$, vous déplacez votre pion sur la case 5, le résultat est OX..OX, la différence de score est $-1$. Par conséquent, le résultat est OX.OOX et la différence de score est $5$.

Pour la deuxième série de tests, un résultat possible est OXOXOXOX, avec une différence de score de $0$. Pour la troisième série de tests, un résultat possible est OX..OXOOOX, avec une différence de score de $-7$. Pour la quatrième série de tests, un résultat possible est OX..OXXXO, avec une différence de score de $8$. Pour la cinquième série de tests, un résultat possible est OXXXOXOO, avec une différence de score de $90$. Pour la sixième série de tests, un résultat possible est OX..OXO.XO, avec une différence de score de $1000000000$.

Entrée 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

Sortie 2

5
13
8
3
9
9