#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005,M=105;
int n,k,Case,s[N],mx[M],l[M],b[N];
int F(int x,int k){if(x<=0)return 0;return (x-1)/k+1;}
void solve() {
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n-k+1;i++)scanf("%d",s+i);
	for(int i=0;i<=k;i++)mx[i]=l[i]=b[i]=0;
	int now=0,sl=0,Mx=0,d=0;
	for(int i=k+1;i<=n;i++)now-=b[i-k],b[i]=s[i-k+1]-s[1]-now,now+=b[i];
	for(int i=1;i<=n;i++)mx[i%k]=max(mx[i%k],b[i]),l[i%k]=max(l[i%k],-b[i]);
	for(int i=0;i<k;i++)sl+=l[i],Mx=max(Mx,l[i]+mx[i]);
	for(int i=0;i<k;i++)d+=Mx-mx[i]-l[i];
	printf("Case #%d: %d\n",++Case,Mx+F(((s[1]-sl)%k+k)%k-d,k));
}
int main() {
	int tt;scanf("%d",&tt);
	while(tt--)solve();
	return 0;
}