Cirno 有一个长度为 $$$n$$$ 的序列 $$$a$$$。她可以执行以下两个操作中的任何一个(可能是零次),除非 $$$a$$$ 的当前长度是 $$$1$$$:
- 反转顺序。形式上,$$$[a_1,a_2,\ldots,a_n]$$$ 在操作后变为 $$$[a_n,a_{n-1},\ldots,a_1]$$$。
- 将序列替换为其差异序列。形式上,$$$[a_1,a_2,\ldots,a_n]$$$ 在操作后变为 $$$[a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]$$$。
求 $$$a$$$ 经过所有操作后元素的最大可能总和。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 输入测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 50$$$) — 序列 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i|\le 1000$$$) — 序列 $$$a$$$。
输出
对于每个测试用例,打印一个表示最大可能总和的整数。
示例
输入 #1
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
输出 #1
-1000 8 1001 2056 269891
注意
在第一个测试用例中,Cirno 无法执行任何操作,因此答案是 $$$-1000$$$。
在第二个测试用例中,琪露诺首先反转序列,然后用其差异序列替换该序列:$$$[5,-3]\to[-3,5]\to[8]$$$。可以证明这使得总和最大化,所以答案是$$$8$$$。
在第三个测试用例中,琪露诺可以选择不操作,所以答案是$$$1001$$$。