Migrated from Lutece 681 Complete Building the House

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bear has a large, empty ground for him to build a home. He decides to build a row of houses, one after another, say $n$ in total. The houses are designed with different height. Bear has m workers in total, and the workers must work side by side. So at a time bear can choose some continuous houses, no more than $m$, and add their heights by one, this takes one day to finish.

Given the designed height for each house, what is the minimum number of days after which all the houses’ heights are equal to the design?

Input

The first line of input contains a number $T$, indicating the number of test cases. ($T\leq 50$)

For each case, the first line contains two integers $n$ and $m$: the number of houses and the number of workers($1\leq n,m\leq 100,000$). The next line comes with $n$ numbers, they are the heights of the houses from left to right.($0\leq height\leq 1,000,000,000$)

Output

For each case, output Case #i: first. ($i$ is the number of the test case, from $1$ to $T$). Then output the days when bear’s home can be built.

Samples

2
3 3
1 2 3
3 3
3 2 1

Case #1: 3
Case #2: 3

Resources

11th UESTC Programming Contest Preliminary