MZL's munhaff function

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.

Sample Input

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

Sample Output

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

Source

2015 Multi-University Training Contest 5