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。