★★比赛新机制★★
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述


最近， 教授研发了一种新的比赛机制，这种比赛机制是 赛制的扩展，简称 。参赛者为个人参赛(即每人一台电脑)，且成绩分为两部分，过题数和罚时。每道题目的罚时 与比赛已经开始的时间(按分钟计) 以及该题错误的提交次数(不包括编译错误) 有关，即 。

另外，新赛制规定，每位参赛者必须按一定的顺序循环做题，直到解出全部题目或比赛结束。在比赛开始之前，每位参赛者可以任意选择第一个要做的题目和方向：正序或者逆序，但是中途不能跳题或者改变方向。例如，现在有 五道题目，参赛者可以选择第一个要做的题目 ，然后按正序 的顺序做题，或者按逆序 的顺序做题，而 或 都是不被允许的。

水平非常高，她总是可以做出所有的题目。现在她想知道，如果已知解决每道题需要花费的时间，那么解决 道题的最少罚时是多少。我们认为比赛时间足够 解决所有题目，在比赛开始的瞬间 就开始做题并且所有题目都是一次提交便成功通过。

输入描述:

第一行一个整数 ，表示测试用例的数量。
对于每组测试用例，第一行一个整数 ，表示题目的数量；
接下来一行  个整数，第  个整数 ，表示解决第  道题需要花费的时间(按分钟计)。
对于全部测试用例，保证 。

输出描述:

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

输入

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

输出

复制 
36
277

说明

在第一组测试用例中， 按题目编号 2,1,5,3,4的顺序做题，总罚时最少，为 。
在第二组测试用例中，总罚时最少为 。