問題文

長さ $N$ の整数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます．ここで，$N \geq 3$ が成り立ちます．
あなたは $1 \leq i < j < N$ を満たす $2$ つの整数 $i, j$ を選択します．このとき，あなたのスコアは $|A_1 + A_2 + \cdots + A_i| + |A_{i + 1} + A_{i + 2} + \cdots + A_j| + |A_{j + 1} + A_{j + 2} + \cdots + A_N|$ となります．

あなたが獲得することのできるスコアの最大値を求めてください．

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください．

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$N$
$A_1\ \ A_2\ \ \cdots A_N$

• $1 \leq T \leq 10^5$
• $3 \leq N \leq 2 \times 10^5$
• $-10^9 \leq A_i \leq 10^9$
• 入力はすべて整数
• $1$ つの入力ファイルにおいて $N$ の総和は $5 \times 10^5$ を超えない

出力

各テストケースについて，答えを $1$ 行に出力し，最後に改行してください．

サンプル

3
6
6 5 -4 3 -2 1
3
0 0 0
5
1 1 1 1 1

17
0
5