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

题目背景

新新在课堂上和同学们一起讨论连减表达式的各种可能性，他们想通过添加不同的括号，让结果尽可能地大。

题目描述

新新在研究一个连减式，形如：

如果不加括号直接计算，就是从左到右依次相减。但新新认为这样太无趣了。他想知道：通过添加括号改变运算顺序，最多能让这个表达式的值变成多大？

注意：括号可以任意添加，但不能改变数字的顺序，也不能对数字取反或做其他操作。

输入格式

第一行一个整数 $t$，表示表达式的数量。
接下来 $t$ 组数据：

• 每组第一行一个整数 $n$，表示表达式中数字的个数。
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示表达式中的数字。

输出格式

输出 $t$ 行，每行一个整数，表示对应表达式通过加括号能得到的最大值。

样例

1
4
10 3 2 2

11

数据范围

对于 100% 的数据，
$1 \le t \le 10$，
$1 \le n \le 10^5$，
$1 \le a_i \le 10^5$。