题目描述

假设你是一位勇敢的冒险者，进入了一座神秘的地下迷宫。迷宫中有多个房间（房间连续排成一排，没有环），每个房间里都藏有一颗宝石，宝石的价值可能是正数（表示宝石的珍贵程度），也可能是负数（表示宝石可能被诅咒，持有它会带来损失）。现在你要进入所有的房间，以收集所有宝石，(不可以选择不收集)，为了提高你的总收益，你可以使用一件强大的魔法道具——“反转之镜”。这个镜子可以让你选择一段连续的房间，并将这些房间里所有宝石的价值符号反转（即正数变负数，负数变正数）。现在请你想办法获得最多的宝石价值

输入

输入包含多个测试用例。输入的第一行是一个整数 t（1 ≤ t ≤ 10），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 n ，表示房间数。

每个测试用例的第二行包含 n 个整数 a1, a2, …, an，表示每个房间宝石的初始价值。

• 房间个数范围为 1 ≤ n ≤ 10^5。

• 房间中宝石价值的范围为 -10^4 ≤ ai ≤ 10^4。

输出

输出是一个整数，表示所有房间中宝石价值总和的最大可能，注意每个测试结果换行输出。

示例

示例 1：

input

 3
 3
 -4 -1 -1
 2
 8 5
 5
 -5 5 8 -6 8

output

6
13
22

解释

第一个样例[-4,-1,-1]全部变成[4,1,1]即可

限制

时间限制：1s 空间限制：128MB