This special board consists of $n$ cells, where the value of cell $i$ ($3 \le i \le n$) is a positive integer $a_i$.

You decide to play a game against your teammate. At the start of the game, you occupy cell 1 and place your piece there, while your teammate occupies cell 2 and places their piece there. At this moment, only these two cells are occupied. Both players start with a score of zero.

You move first, and then the players take turns. In each turn, if the current player's piece is at cell $x$, the player must choose a step size $d \in \{1, 2, 3, 4\}$ such that $x + d \le n$ and cell $x + d$ is not yet occupied. The player then adds the value of that cell, $a_{x+d}$, to their score and jumps their piece forward to cell $x + d$. After the jump, the player permanently occupies this new cell. Specifically, if there are no valid jump steps, the player cannot move this turn and must skip it. The game ends when neither player can make a move.

Clearly, both you and your teammate are clever and will adopt optimal strategies during the game. To predict the outcome of the game in advance, you need to calculate the value of your total score minus your teammate's total score at the end of the game.

Input

Each test case contains multiple test sets. The first line contains a positive integer $T$ ($1 \le T \le 10^3$), representing the number of test sets. For each test set:

• The first line contains a positive integer $n$ ($6 \le n \le 10^5$), representing the number of cells on the board.
• The second line contains $n - 2$ positive integers $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$), representing the value of each cell.

It is guaranteed that the sum of $n$ over all test sets does not exceed $10^5$.

Output

For each test set, output a single integer representing the value of your total score minus your teammate's total score.

Examples

Input 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

Output 1

5
0
-7
8
90
1000000000

Note 1

The game results are represented by a string of length $n$, where the character . indicates that the cell is not occupied by anyone, O indicates that the cell is occupied by you, and X indicates that the cell is occupied by your teammate.

For the first test set, in the first turn, you have three choices: Choose step size $d = 2$, jump to cell 3, the game result is OXOXXO, score difference is $-6$; Choose step size $d = 3$, jump to cell 4, the game result is OX.OOX, score difference is $5$; * Choose step size $d = 4$, jump to cell 5, the game result is OX..OX, score difference is $-1$.

Therefore, the game result is OX.OOX, and the score difference is $5$.

For the second test set, one possible game result is OXOXOXOX, with a score difference of $0$.

For the third test set, one possible game result is OX..OXOOOX, with a score difference of $-7$.

For the fourth test set, one possible game result is OX..OXXXO, with a score difference of $8$.

For the fifth test set, one possible game result is OXXXOXOO, with a score difference of $90$.

For the sixth test set, one possible game result is OX..OXO.XO, with a score difference of $1000000000$.

Input 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

Output 2

5
13
8
3
9
9