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$