I. Shooting Stars
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ crystals numbered $$$1$$$ through $$$n$$$ from left to right. Crystal $$$i$$$ initially contains $$$a_i$$$ units of energy. You may collect all $$$n$$$ crystals in any order.

When you collect crystal $$$i$$$:

  • You add its current energy to your total score.
  • If $$$i \gt 1$$$ and crystal $$$i-1$$$ has not yet been collected, its current energy changes sign.
  • If $$$i \lt n$$$ and crystal $$$i+1$$$ has not yet been collected, its current energy changes sign.

The crystals' numbers do not change as you collect them.

What is the maximum total score after collecting all $$$n$$$ crystals?

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$), the number of crystals.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), their initial energies.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output one integer: the maximum possible total score.

Example
Input
2
5
1 2 3 4 5
9
9 -9 8 -2 4 -4 3 -5 3
Output
15
47
Note

Sample 1 Explanation

In the first test case, collecting crystals in the order $$$3 \to 5 \to 1 \to 2 \to 4$$$ gives a score of $$$15$$$. This is optimal.