There are \(n\) children standing in a line, where the niceness of the \(i\)-th child is \(a_i\). Santa is deciding which children belong on the nice list and which belong on the naughty list.

An integer \(X\) is initially set to \(0\). Santa will perform the following operation exactly \(n - 1\) times:

• Choose the first or second child in line and remove them from the line.
• Let \(w\) be the niceness of the chosen child.
  • If the first child was chosen, add them to the nice list and add \(w\) to \(X\).
  • If the second child was chosen, add them to the naughty list and subtract \(w\) from \(X\).

Note that after all operations, exactly one child remains unassigned to a list.

Determine the maximum possible value of \(X\) that Santa can obtain after all \(n - 1\) operations.

Input Specification

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\) (\(2 \le n \le 2 \cdot 10^5\)) — the number of children.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)) — the niceness of each child.

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\).

Output Specification

For each test case, print a single integer — the maximum possible value of \(X\) that Santa can obtain after all \(n - 1\) operations.

Examples

Example Input 1

7
2
2 -3
4
1 4 3 4
4
-4 2 3 -6
5
-2 -3 4 10 -9
5
-12345678 -1000000000 -999999999 1000000000 -999999999
2
-7 1
5
7 -6 -1 -8 -8

Output

3
8
4
15
2987654321
-1
29

Source

Codeforces