蜗蜗有一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。现在他想要选择两段不相交的非空子区间 $[L_1,R_1]$, $[L_2,R_2]$，使得 $(\sum\limits_{i=L_1}^{R_1} a_i) \times (\sum\limits_{j=L_2}^{R_2} a_j)$ 最大，求最大值。

输入格式

第一行包含一个整数 $T$，表示 $T$ 组测试数据。

对于每组测试数据：

第一行包含一个整数 $n$。

接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试数据，输出一行包含一个整数，表示答案。

样例输入 1

3
5
-20 10 30 20 -20
2
-1234 5678
9
-9 9 -8 2 -4 4 -3 5 -3

样例输出 1

800
-7006652
90

样例2-5

见附件文件。样例 2-5 分别满足子任务 1-4 的限制。

数据范围

本题采用捆绑测试。

子任务 1（20分）：$n,\sum n \leq 50$。

子任务 2（20分）：$n,\sum n \leq 500$。

子任务 3（20分）：$0 \leq a_i \leq 10^4$。

子任务 4（40分）：无特殊限制。

对于所有数据，保证 $1 \leq T \leq 10^5$, $2 \leq n, \sum n \leq 2 \cdot 10^5$, $-10^4 \leq a_i \leq 10^4$。