Adamma 是一位对温度感兴趣的气候科学家。每一分钟，她都会记录当前的温度作为一个整数，从而得到一个长整数序列：x₁, x₂, ..., x_N。（Adamma 使用她自己独特的温标，而不是摄氏度或开尔文等常见的温标，因此数值可能是很大的负数！）她经常在电脑屏幕上绘制这些温度的曲线图。

今天早上，她决定计算该序列的滑动平均值，以便得到更平滑的曲线图。她使用了一个大小为 K 的平滑窗口，这意味着她将 N 个温度的序列转换为了 (N - K + 1) 个平均温度的序列：s₁, s₂, ..., s_N-K+1。 每个 s_i 都是 x_i, x_i+1, ..., x_i+K-1 这些值的平均值。原始的 x_i 值均为整数，但某些 s_i 可能是分数。

不幸的是，Adamma 忘记保存原始的温度序列了！现在她想回答一个不同的问题——最高温度和最低温度之间的差值是多少？换句话说，她需要计算 max{x₁, ..., x_N} - min{x₁, ..., x_N}。 但她只拥有 N、K 以及平滑后的序列。

经过思考，Adamma 意识到这可能是不可能的，因为可能存在多个有效的答案。在这种情况下，她想知道在所有能够产生她所给出的平滑序列（对于给定的 N 和 K）的原始序列中，最小可能的差值是多少。

输入格式

输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例；每个测试用例包含两行。第一行包含由空格分隔的整数 N 和 K。第二行包含由空格分隔的整数值 sum₁, sum₂, ..., sum_N-K+1。 其中 s_i 由 sum_i / K 给出。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 x 是测试用例编号（从 1 开始），y 是最高温度和最低温度之间最小可能的差值。

数据范围

内存限制：1 GB。

1 ≤ T ≤ 100。

2 ≤ K ≤ N。

sum_i 为 -10000 到 10000 之间的整数（包含边界）。

小数据集（6 分）

时间限制：10 秒。

2 ≤ N ≤ 100。

大数据集（7 分）

时间限制：20 秒。

2 ≤ N ≤ 1000。

2 ≤ K ≤ 100。

样例

样例输入 1

3
10 2
1 2 3 4 5 6 7 8 9
100 100
-100
7 3
0 12 0 12 0

样例输出 1

Case #1: 5
Case #2: 0
Case #3: 12

说明

在 Case #1 中，平滑后的序列为：

0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5

得到最小差值的整数序列为：

0, 1, 1, 2, 2, 3, 3, 4, 4, 5

请注意，序列：

0.5, 0.5, 1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 4.5, 4.5

虽然会产生相同的平滑序列且最大差值为 4，但这不是一个有效答案，因为原始温度已知必须为整数。

在 Case #2 中，我们只知道 100 个原始值的总和为 -100。原始值可能全部恰好为 -1，在这种情况下，最高温度和最低温度之间的差值为 0，这是差值所能达到的最小值！

在 Case #3 中，原始序列可能是：

-4, 8, -4, 8, -4, 8, -4