You are given $N integers A_{1}, A_{2}, \ldots, A_{N}$.

You can perform the following operation any number of times:

Select any index i such that 1 ≤ i ≤ (N-1);
Subtract 1 from A_{i} and 2 from A_{i+1}.

Find the smallest possible value of $|A_{1}| + |A_{2}| + \ldots + |A_{N}|$ you can achieve after performing any number of given operations.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N — the number of integers.
• The second line of each test case contains $N integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

For each test case, output a single integer — the smallest possible value of $|A_{1}| + |A_{2}| + \ldots + |A_{N}|$ you can achieve after performing any number of given operations.

------ Constraints ------

$1 ≤ T ≤ 100000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$-10^{9} ≤A_{i} ≤10^{9}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
4
2
2 4
3
1 1 1
6
-4 2 -4 2 -4 2
1
-100000000

----- Sample Output 1 ------
0
2
15
100000000

----- explanation 1 ------
Test case $1$: We can apply the operation for $i = 1$. Thus, the array becomes $A = [1, 2]$. On applying the operation again for $i=1$, the array becomes $A = [0, 0]$. Thus, the value of $|A_{1}| + |A_{2}| = 0$. It can be shown that this is the smallest possible value of $|A_{1}| + |A_{2}|$.

Test case $2$: Apply the operation for $i = 1$. The array becomes $A = [0, -1, 1]$. Thus, the value $|A_{1}+|A_{2}|+|A_{3}| = 0+1+1 = 2$.

Test case $3$: We apply three operations on indices $1, 3,$ and $5$ respectively. Thus, the final array becomes $A = [-5, 0, -5, 0, -5, 0]$. The value $|A_{1}| + |A_{2}| + \ldots + |A_{6}| = 15$.

Test case $4$: We cannot apply any operation on the array as we cannot choose any valid index.

见题面

见题面