E. Swap and Negate
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

You are allowed to perform the following operation on the array $$$a$$$ any number of times (including zero):

  • Choose an index $$$i$$$ such that $$$1 \le i \lt n$$$;
  • Set $$$a_i := -a_{i+1}$$$ and $$$a_{i+1} := -a_i$$$ simultaneously.

Determine the maximum possible sum of all elements in the array that can be achieved by performing the operations optimally.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the length of the array $$$a$$$.

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

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

Output

For each test case, print a single integer — the maximum possible sum of the array elements after performing the operations any number of times.

Example
Input
4
1
-3
4
1 -2 -3 4
5
-10 1 0 1 -10
2
6 -7
Output
-3
10
18
1
Note

For the first test case, no operation can be performed. Hence, the maximum sum will be equal to $$$-3$$$.

For the second test case, choosing $$$i = 2$$$ makes the array $$$a = [1, 3, 2, 4]$$$. Now, the sum of all the elements is equal to $$$10$$$. It can be shown that this is the maximum possible.