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:

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

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

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

First or Second

Examples