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

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,\ldots,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

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

Note

In the first test case, Santa will perform exactly one operation. If he chooses the first child, he will add $a_1=2$ to $X$ to get $X=2$; if he chooses the second child, he will subtract $a_2=-3$ from $X$ to get $X=3$. Thus, the answer is $3$.

In the second test case, it is optimal to select the first child in all three operations. The value of $X$ will be $1+4+3=8$.

In the third test case, below is an optimal sequence of operations:

#TypeNiceness of remaining children$X$ after operation0—$[-4, 2, 3, -6]$$0$1First$[2, 3, -6]$$-4$2First$[3, -6]$$-2$3Second$[3]$$4$

In the fourth test case, below is an optimal sequence of operations:

#TypeNiceness of remaining children$X$ after operation0—$[-2, -3, 4, 10, -9]$$0$1Second$[-2, 4, 10, -9]$$3$2First$[4, 10, -9]$$1$3First$[10, -9]$$5$4First$[-9]$$15$