Time Limit: 2.0 s

Memory Limit: 512.0 MB

Description

There is a tunnel having \(N\) equal segments. In each of the ith segment there is a monster having a destructive power of \(Ai\).

Thakur wants to kill all the monsters.
Each time Thakur enters the tunnel he has two options for a monster in each segment. Either fight and kill the monster immediately or do nothing.

If he chose to do nothing in the \(i\)th segment then he will be harmed by the \(i\)th monster, which means his health will be decreased by \(Ai\) only if the monster is alive. Obviously a dead monster cannot harm him.

Or, if he choses to fight with the \(i\)th monster his health remains same because Thakur can kill a monster before the monster does any harm to him. After fighting a monster Thakur can not fight in next two segments. So, if he fights in \(i\)-th segment then he can not fight with the \(i+1\) and \(i+2\) th monster, that means, he will be harmed by those monsters if they are alive.

Thakur can enter the tunnel from any side as many time as he wants but he has to come out from the tunnel from the opposite side of his entrance. Which means Thakur cannot go backward in any situation. If he enters the tunnel from left side he has to come out from right side and vice versa.

What is the minimum amount of health Thakur has to lose to kill all the monsters, given that Thakur has enough amount of health.

Input

First line takes an integer \(T\) : number of testcases
first line of each testcase takes an integer \(N\) : number of monsters/segments in the tunnel
second line takes \(N\) integer \(A1,A2,A3....An\) : destruction power of each monster

\(1 <= T <= 10^4\)
\(3 <= N <= 2*10^5\)
\(1 <= Ai <= 10^9\)
sum of \(N\) over all testcase will not exceed \(2*10^5\)

Output

print an integer in each testcase : minimum amount of health Thakur has to lose to kill all the monsters

Sample

2
5
5 5 6 5 6
5
5 100 5 50 100

22
65

In the first testcase:

Thakur will enter the tunnel 3 time from left side
in first turn,
he will fight with monster in position 2 and 5
so he will be harmed by monster 1,3,4 and lose health 5+6+5 = 16
in second turn,
he will fight with monster in position 1,4 and harmed by monster 3 only. (other monsters were killed in the first turn)
and lose health 6
in third turn,
he will fight the only monster alive in position 3 without losing any health.
so he will lose 16+6+0 = 22 health in 3 turn.
he can not kill all the monsters without losing at least 22 health.