Problem Description

MZL is a mysterious mathematician, and he proposed a mysterious function at his young age.
Stilwell is very confused about this function, and he need your help.
First of all, given $n$ positive integers $A_i$ and $A_i\geq A_{i+1}$.
Then, generate $n$ positive integers $B_i$
$$B_i=\sum_{j=i}^nA_j$$
Define $f(i,j)$ for $i,j\in Z$
$$
f(i,j)=\left\{\begin{matrix}
0 & & (i,j)=(1,1)\\
min(f(i-1,j+1),f(i,\lceil\frac{j}{2}\rceil)+B_i) & & i,j\in[1,n],~(i,j)\neq(1,1) \\
10^{11037} & & otherwise
\end{matrix}\right.
$$
Find $f(n,1)$.

Input

The first line of the input contains a single number $T$, the number of test cases.
For each test case, the first line contains a positive integer $n$, and the next line contains $n$ positive integers $A_i$.
$T\leq 100$, $1\leq n\leq 10^5$, $\sum n\leq 10^6$, $1\leq A_i\leq 10^4$.

Output

For each test case, output $f(n,1)$ in a line.

3
3
1 1 1
5
28 26 25 24 1
10
996 901 413 331 259 241 226 209 139 49

5
233
11037

Hint

case 1 ：
f(1,1)=0
f(1,2)=f(1,1)+3=3
f(1,3)=f(1,2)+3=6
f(2,1)=min(f(2,1)+2,f(1,2))=3
f(2,2)=min(f(2,1)+2,f(1,3))=5
f(2,3)=f(2,2)+2=7
f(3,1)=min(f(3,1)+1,f(2,2))=5

Author

SXYZ