题目描述

每次测试的时间限制：$2$ 秒 每次测试的内存限制：$512$ 兆字节

琪露诺有一个长度为 $n$ 的序列 $a$。她可以执行以下两种操作中的任意一种任意次（可能为零次），除非当前序列 $a$ 的长度为 $1$：

反转序列。形式化地说，$[a_1, a_2, \dots, a_n]$ 经过操作后变为 $[a_n, a_{n-1}, \dots, a_1]$。

将序列替换为其差分序列。形式化地说，$[a_1, a_2, \dots, a_n]$ 经过操作后变为 $[a_2 - a_1, a_3 - a_2, \dots, a_n - a_{n-1}]$。

求经过若干次操作后，序列 $a$ 的元素之和的最大可能值。

输入

第一行包含一个整数 $t$（$1 \leq t \leq 100$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 50$）——序列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \leq 1000$）——序列 $a$。

一个数 $n$。

输出格式

对于每个测试用例，输出一个整数，表示可能的最大和。

5
1
-1000
2
5 -3
2
1000 1
9
9 7 9 -9 9 -8 7 -8 9
11
678 201 340 444 453 922 128 987 127 752 0

-1000
8
1001
2056
269891

提示

在第一个测试用例中，琪露诺无法执行任何操作，因此答案是 $-1000$。

在第二个测试用例中，琪露诺先反转序列，然后将其替换为差分序列：$[5, -3] \to [-3, 5] \to [8]$。可以证明这能使和最大，因此答案是 $8$。

在第三个测试用例中，琪露诺可以选择不进行操作，因此答案是 $1001$。