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

Description

给你一个数组，你可以多次进行以下两个操作，求操作结束后数组的最大和

• 翻转整个数组，例如 $[a_1, a_2, a_3]$ 会变成 $[a_3, a_2, a_1]$
• 用数组的差分数组代替它，例如 $[a_1, a_2, a_3]$ 会被 $[a _1 - a_2, a_2 - a_3]$ 代替

Format

Input

第一行输入一个 $t$ 表示测试用例数量

对于每个测试：

第一行输入一个 $n$ 表示数组 $a$ 的大小

第二行输入 $n$ 个数字表示 $a_i$

Output

一个表示最大可能总和的整数

Samples

2
1
10
2
-2 1

10
3

Limitation

$1 \leq t \leq 100$

$1 \leq n \leq 50$

$1 \leq \vert a_i \vert \leq 1000$