题目描述

小 D 在数学课上看到了这样一个表达式：

如果不加括号，计算机默认从左到右依次计算。但通过添加括号，可以改变运算顺序，从而得到不同的结果。

例如对于 $10 - 3 - 2 - 2$：

• 不加括号：$(((10 - 3) - 2) - 2) = 3$
• 加括号为 $10 - (3 - 2 - 2)$：$10 - (3 - 2 - 2) = 10 - (-1) = 11$

小 D 想知道，给定若干组表达式，通过合理添加括号，每组表达式能得到的最大值是多少？

注意：括号可以任意添加、嵌套，但不能改变数字的顺序，也不能添加负号或做其他变换。

输入格式

第一行一个整数 $T$，表示表达式的组数。

接下来共 $2T$ 行，每组表达式占两行：

• 第一行一个整数 $n$，表示该组表达式中数字的个数；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示表达式中的数字（按原顺序）。

输出格式

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

样例

3
1
7
2
10 3
4
10 3 2 2

7
7
11

样例解释

第一组表达式只有一个数 $7$，无法加括号，结果就是 $7$。

第二组表达式为 $10 - 3$，无法通过加括号改变结果，答案为 $7$。

第三组表达式为 $10 - 3 - 2 - 2$，加括号为 $10 - (3 - 2 - 2) = 11$，答案为 $11$。

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$1 \le n \le 10^5$，$1 \le a_i \le 10^5$。所有表达式的 $n$ 之和不超过 $2 \times 10^5$。