A - ★★比赛新机制★★

时间限制： 1000ms

空间限制： 256MB

题目描述

最近，Allen 教授研发了一种新的比赛机制，这种比赛机制是 ACPC
(AsiaCollegiateProgrammingContest) 赛制的扩展，简称
AUPC(AsiaUniversityProgrammingContest)。参赛者为个人参赛(即每人一台电脑)，且成绩分为两部分，过题数和罚时。每道题目的罚时 $s$ 与比赛已经开始的时间(按分钟计) $a$ 以及该题错误的提交次数 $b$ (不包括编译错误)有关，即$s=a+b×20$
另外，新赛制规定，每位参赛者必须按一定的顺序循环做题，直到解出全部题目或比赛结束。在比赛开始之前，每位参赛者可以任意选择第一个要做的题目和方向：正序或者逆序，但是中途不能跳题或者改变方向。例如，现在有
$A,B,C,D,E$ 五道题目，参赛者可以选择第一个要做的题目
C，然后按正序
$C,D,E,A,B$ 的顺序做题，或者按逆序
$C,B,A,E,D$ 的顺序做题，而
$C,D,B,A,E$ 或
$C,E,A,B,D$ 都是不被允许的。
Alice 水平非常高，她总是可以做出所有的题目。现在她想知道，如果已知解决每道题需要花费的时间，那么解决
$n$ 道题的最少罚时是多少。我们认为比赛时间足够
Alice 解决所有题目，在比赛开始的瞬间
Alice 就开始做题并且所有题目都是一次提交便成功通过。

输入描述:

第一行一个整数 $T$ : ($1 \leq T \leq 5 \times 10^{5}$)，表示测试用例的数量。对于每组测试用例，第一行一个整数 $n$  ($1\leq n \leq5 \times 10^{5}$)，表示题目的数量；接下来一行 $n$ 个整数，第 $i$ ($1 \leq i \leq n$) 个整数 $Ai$  ($1≤Ai≤5\times 10^{5}$)，表示解决第 $i$ 道题需要花费的时间(按分钟计)。对于全部测试用例，保证 $\sum n \leq 5 \times 10^{5}$.

输出描述:

对于每组测试用例，输出一行一个整数表示答案。

示例

输入

2
5
2 1 5 3 4
10
5 9 3 7 8 1 10 4 6 2

输出

36
277

说明

在第一组测试用例中，$Alice$ 按题目编号 $2,1,5,3,4$的顺序做题，总罚时最少，为 $1+3+7+10+15=36$。
在第二组测试用例中，总罚时最少为 $5+7+13+17+27+28+36+43+46+55=277$。