题目背景

现在有一个由 $n$ 个元素组成的数组 $a$ ，对该数组可以进行两种操作（先进行第一种，在进行第二种）：

• $1、$ 将数组进行重新排列，或者保持不变。

• $2、$ 最多选择一个连续的元素段，并将该元素段中所有元素的符号替换为相反符号。比如我们选择一对索引 $l, r, (1 \leq l \leq r \leq n)$ 将 $l \leq i \leq r$ 中所有的 $a_i = -a_i$ ，同样也可以不选择，保持元素不变。

题目描述

现在给定 $n$ 个元素组成的数组 $a$ ，然后进行以上两次操作，请问最终数组的最大和是多少？

输入格式

输入多行。

第一行输入一个 $t$ ，代表有 $t$ 组测试数据。

对于每一组测试数据，第一行输入一个正整数 $n$ ，代表元素个数；第二行输入 $n$ 个整数 $a_i$ 。

输出格式

输出多行。

对于每一组测试数据，输出操作之后的最大数组之和。

样例 #1

样例输入 #1

8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12

样例输出 #1

8
0
1
99
22
15
270
78

提示

样例解释】：

• 对于第一组测试样例：先将数组重新排列为 3 -2 -3 ，然后选择 $2$ 到 $3$ 的区间进行翻转元素变成 3 2 3 最终的和为 $8$ 。

数据范围】：

对于 $100\%$ 的数据，保证 $1 \leq t \leq 10^3, 1 \leq n \leq 10^{6}, -10^9 \leq a_i \leq 10^9$​​ 。