该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

炼金术士拥有 “点石成金” 的能力，他有 $n$ 个神奇的材料。这种材料有冰属性和火属性两种属性，这两种属性在一起会相互湮灭，但炼金术士可以使连续的两个材料的属性同时取反。每个材料都有自己的属性值 $A_{i}$，我们用正数表示火属性材料的属性值，用负数表示冰属性材料的属性值。由于炼金术士的目标是获得火属性的材料，那么他应该怎么操作才能获得最多的火属性材料。

输入格式

第一行输入一个正整数 $T$。

接下里 $T$ 组数据，每组两行。

第一行输入一个正整数 $n$ 。

第二行输入 $n$ 个整数，其中正数表示火属性材料的属性值，负数表示冰属性材料的属性值。

输出格式

输出 $T$ 行，每行一个整数，表示你可以获得的最大的火属性材料值。由于可能无法获得火属性材料，此时输出最小的冰属性材料值。

样例

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,5,-(-5),-0,2]=[1,5,5,0,2]$ 的方式，来使得相加得到 $13$ ,为最大的火属性值。

对于 $100\%$ 的数据有，$2\le n\le 2\cdot10^{5}$ , $-10^{9}\le A_{i}\le10^{9}$。

我们保证所有的 $n$ 之和不会超过 $2\cdot10^{5}$。