Mix and Merge

You are given an array $A$ of $n$ elements and a constant $k$. You can perform the following operation on the array —

• Choose any sub-array of $p$ elements where $2 \le p \le k$ and merge the elements into a new element. The $p$ elements are removed and their sum is inserted as a new element in that place. The cost of this operation is the sum itself.

Calculate the minimum cost to reduce the array to only one element, by performing the mentioned operation as many times needed.

Input

First line of input will contain an integer $T$ denoting the number of test cases.

For each test case, the first line contains two integers $n$ and $k$, and the second line contains $n$ integers $A_1, ~A_2, \dots A_n$.

Constraints:

• $1 \le T \le 100$.

• $1 \le n \le 100$.

• $2 \le k \le 50$.

• $1 \le A_i \le 100$.

Output

For each test case, output a line in the format “Case i: x” without the quotes, where $x$ is the minimum cost to reduce the array to only one element, by performing the mentioned operation as many times needed.

Sample

Input	Output
1 4 3 1 2 3 4	Case 1: 13