SCNUOJ 传题人注：本题背景为第 45 届 ICPC 银川区域赛作弊事件。

最近，Allen 教授研发了一种新的比赛机制，这种比赛机制是 ACPC (Asia Collegiate Programming Contest) 赛制的扩展，简称 AUPC (Asia University Programming Contest)。参赛者为个人参赛（即每人一台电脑），且成绩分为两部分，过题数和罚时。每道题目的罚时 $s$ 与比赛已经开始的时间（按分钟计） $a$ 以及该题错误的提交次数（不包括编译错误）$b$ 有关，即 $s=a+b \times 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 \leq 5 \times 10^{5})$，表示题目的数量；

接下来一行 $n$ 个整数，第 $i \ (1 \leq i \leq n)$ 个整数 $A_{i} \; (1 \leq A_{i} \leq 5 \times 10^{5})$，表示解决第 $i$ 道题需要花费的时间（按分钟计）。

对于全部测试用例，保证 $\sum n \leq 5 \times 10^5$。

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

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

在第二组测试用例中，总罚时最少为 $5+7+13+17+27+28+36+43+46+55=277$。