M. Maximum Subarray Alternating Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The secret partner got tired of the difficult problems Eddard kept adding to the contest, and decided to take matters into their own hands once again and add an easy classical problem, the maximum subarray sum: "Given an array $$$a$$$ of $$$n$$$ integers, find the maximum sum of any subarray."

But, of course, Eddard decided to sabotage the problem and make it a little harder. After all, why shouldn't he? Now, the problem is the maximum subarray alternating sum.

The alternating sum $$$S$$$ of an array $$$b$$$ is given as follows:

$$$S(b) = b_1 - b_2 + b_3 - ... + (-1)^{n + 1} \cdot b_n$$$.

In other words, $$$S(b) =$$$ sum of elements with odd indices $$$-$$$ sum of elements with even indices.

For example, for $$$a = [3, 7, 1, 5]$$$:

$$$S(a_{2..4}) = a_2 - a_3 + a_4 = 7 - 1 + 5 = 11$$$, which is also the maximum subarray alternating sum.

$$$S(a_{1..2}) = a_1 - a_2 = 3 - 7 = -4$$$.

Can you find the maximum subarray alternating sum of the array?

Input

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

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ – The size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \le a_i \le 10^9)$$$ – The elements of the array.

Output

For each test case, print a single integer, the maximum subarray alternating sum of the array $$$a$$$.

Example
Input
3
4
3 7 1 5
5
1 0 1 0 1
3
1 4 24
Output
11
3
24