共有 $T$ 个测试用例，每个测试用例内容如下：

给定一组 $n$ 个整数： $A=\left\{a_{1},a_{2},…,a_{n}\right\}$ ，我们定义函数 $d(A)$ 如下：

在 $A$ 中选取两个没有重复部分的子段，并各自求和，使得两个子段的和的差最大，这个值即为需要求出的 $d(A)$ 的值。独特的是：$A$ 是首尾相接的。

$d(A)=max\left\{\left|\sum_{i=s_{1}}^{t_{1}} a_{i}-\sum_{j=s_{2}}^{t_{2}} a_{j}\right|\right\}$
$(1≤s_{1}$ , $t_{1}$ , $s_{2}$ , $t_{2}≤n$ , $t_{1}<s_{2})$

我们需要求出 $d(A)$ 的值。

第 $1$ 行：一个整数 $T$ ，表示测试用例数。
第 $2$ ~ $T+1$ 行：
偶数行:一个整数 $n$ ，表示 $A$ 的长度。
奇数行:上一个偶数行的 $n$ 的值个数，表示 $A$ 的每一项。

第 $1$ ~ $T$ 行：每个测试用例得出的 $d(A)$ 的值。

$T≤30$ , $2≤n≤50000$ , $\left|a_{i}\right|≤10000$ 。