You are given an array  $A$ of size $N$. You can fix any element, say $K$ of the array and all the elements in the array greater than or equal to $K$ become $K$ and all the elements less than $K$ multiplied by -1. You have to find the maximum sum of the array after fixing $K$ .

Input Format

The first line contains T, the number of test cases.
For each Test case :
The first line contains an integer N, size of the array.
The second line contains N space-separated integers, the $i^{th}$ of which is $A[i]$.

Input Constraints

$1 \le T \le 10^{ 5}$
$2 \le N \le 10^{5}$
$0 \le A[i] \le 10^{6}$
Sum of N all over testcases doesn't not exceed $10^{6}$.

Output Format

For each test case, print the maximum sum of the array by fixing an element $K$.
Answer for each test case should come in a new line.

Note

Candidates are expected to write complete code of searching, sorting etc. (if they are being used in the code) instead of using builtin functions provided by the language library.
Using builtin functions may lead to disqualification from the shortlisting process.