#422 Merge Alarm

Statement

Statement language

There are $N$ signal pieces in a row. Initially, every piece has displayed value $1$ .

Boundary $i$ lies between the original pieces $i$ and $i+1$ . Its alarm cost is $C_i$ .

Merging consecutive signal pieces creates a bundle. Every bundle consists of a contiguous interval of original pieces and has one displayed value between $0$ and $M-1$ .

Choose a boundary $i$ that has not been removed and merge the two bundles adjacent to it. Let their displayed values be $x$ and $y$ .

If $x+y<M$ , the new bundle has displayed value $x+y$ .
If $x+y\geq M$ , an alarm occurs at boundary . You pay , and the new bundle has displayed value .

The chosen boundary is removed and cannot be used again. Perform exactly $N-1$ merges until all pieces form one bundle.

Find the minimum possible total alarm cost.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum possible total alarm cost on one line.

Constraints

$1 \leq T \leq 150\,000$ .
$2 \leq N \leq 300\,000$ .
$2 \leq M$ .

Subtasks

#	Score	Constraints
1	23	$N \leq 10$ . The sum of $N$ over all test cases does not exceed $500$ .
2	8	$M>N$ .

Samples

Input

1
8 3
8 2 6 1 7 3 5

Output

3

Removing boundaries in the order $1,2,5,4,7,6,3$ makes alarms occur only at boundaries $2$ and $4$ . The total cost is .