Years later, Shiro and White both enrolled in THU. After learning about the EXP3 algorithm for the "Multi-armed Bandit" problem in class, they suddenly had a whim and devised a game unrelated to this.

There are $n$ positions arranged in a row, numbered $1,2,\ldots,n$ from front to back. Each position can be in one of two states: blackened or unblackened. Shiro's piece starts at position $1$, and White's piece starts at position $2$. At the beginning of the game, only positions $1$ and $2$ are blackened.

The players take turns making moves, with Shiro going first. In each turn, the current player must choose their own piece and jump forward $1$ to $4$ steps to an unblackened position, and blacken the position they land on. If a player cannot make a legal move (i.e., all positions within $1$ to $4$ steps forward from their current position are either beyond $n$ or already blackened), the player will skip this turn (i.e., make no move).

The game ends when both Shiro and White cannot make any valid move. It is easy to prove that the game is guaranteed to terminate within a finite number of steps.

For each $3\le k\le n$, position $k$ has a positive integer weight $a_k$. Whenever a player blackens such a position $k$, their score increases by $a_k$. Both Shiro and White start with a score of $0$, and both of them aim to maximize the difference between their own score and their opponent's score by the end of the game.

Let $d=s_1 - s_2$, where $s_1$ is Shiro's score and $s_2$ is White's score. Shiro and White want to know: if both players act according to optimal strategies, what will be the value of $d$ after the game ends? Since this problem is too complex, they have turned to you from THUSAA. You have to help them solve the problem.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($6\le n\le 10^5$) — the number of positions.

The second line contains $n-2$ integers $a_3, a_4, \ldots, a_n$ ($1\le a_i\le 10^9$) — the weights of positions $3$ to $n$.

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

Output

For each test case, output a single integer — the final value of $d$.

Note

The following is the explanation for the first example test:

We use the character O to denote a position that has not been visited by anyone, S to denote a position visited by Shiro, and W to denote a position visited by White. Then, the final configuration can be represented by a string of length $n-2$, and this string uniquely corresponds to the sequence of moves made by both players.

For the first test case, consider Shiro's first move as the starting player:

• She cannot move to position $2$, because it is already occupied by White;
• If her first move is to position $3$, then the final state is SWWS (score difference is $-6$);
• If her first move is to position $4$, then the final state is OSSW (score difference is $5$);
• If her first move is to position $5$, then the final state is OOSW (score difference is $-1$);

Therefore, the optimal final state is OSSW, with a score difference of $5$.

For the second test case, one possible final state is SWSWSWSW, with a score difference of $0$.

For the third test case, White can secure the farthest position $10$ in two moves, which Shiro cannot reach. Therefore, one possible strategy for Shiro is to make a large forward move to prevent White from delaying further. The corresponding final state is OOSWSSSW, with a score difference of $-7$.

For the fourth test case, one possible final state is OOSWWWS, with a score difference of $8$.

For the fifth test case, one possible final state is WWSWSS, with a score difference of $90$.

For the sixth test case, one possible final state is OOSWSOWS, with a score difference of $1\,000\,000\,000$.