题目描述

给定一个由 $n$ 个元素组成的数组 $a$，在执行以下操作任意次数后，找到该数组可能具有的最大和：

选择两个相邻元素并翻转它们的符号。换句话说，选择索引 $i(1≤i≤n−1)$，并赋值 $a_i=-a_i$ 和 $a_{i+1}=-a_{i+1}$。

输入格式

输入由多个测试用例组成。第一行包含整数 $t(1≤t≤1000)$ 代表测试用例数。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(2≤n≤2×10^5)$ 代表数组的长度。

下一行包含 $n$ 个空格分隔的整数 $a_1,a_2,…,a_n(-10^9≤a_i≤10^9)$。

保证所有测试用例的 $n$ 之和不超过 $2×10^5$。

输出格式

对于每个测试用例，在执行所述操作任意次数后，输出数组可能具有的最大总和。

测试样例

5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1

1
13
6
39
2

样例说明

对于第一个测试用例，通过对前两个元素执行操作，我们可以将数组从 $[-1,-1,-1]$ 更改为 $[1,1,-1]$，可以证明该数组获得的最大可能和为 $1+1+(−1)=1$。

对于第二个测试用例，通过对 $-5$ 和 $0$ 执行操作，我们将数组从 $[1,5,-5,0,2]$ 更改为 $[1,5,5,0,2]$，这是最大的和，因为所有元素都是非负的。因此，答案是 $1+5+5+0+2=13$。

对于第三个测试用例，数组已经只包含正数，因此不需要执行操作。答案只是整个数组的总和，即 $1+2+3=6$。