House Man

时间限制：2 秒 / 内存限制：32 MB

Description

在福州，有一个疯狂的超人。他不会飞，但他可以从一栋房子跳到另一栋房子屋顶上。今天，他打算用 $N$ 栋房子来锻炼他的跳跃技巧。

他会从最矮的房子开始，进行 $N-1$ 次跳跃，每次跳跃都必须跳到比当前所在房子更高的房子上。最终，他会恰好访问每栋房子一次，且以从矮到高的顺序跳跃，最后到达最高的房子。

他每次跳跃在水平方向上的最大跳跃距离为 $D$。为了让训练更有趣，这位超人希望最矮的房子和最高的房子之间的距离尽可能大。

这位超人还有一个特殊能力——他可以移动房子。于是他打算按照以下规则重新安排这些房子的相对位置：

1. 所有房子只能沿一维路径移动；
2. 所有房子必须被放置在整数坐标上，且每个位置不能有两栋房子；
3. 房子的左右顺序必须与输入中给出的顺序完全一致，不能按高度排序或重新排序；
4. 每栋房子到下一栋更高房子的水平距离不能超过 $D$。

现在给出每组测试数据中的房屋顺序和高度，请帮这位超人计算在满足以上规则的前提下，最矮和最高房子之间的最大水平距离。如果无法满足要求，输出 -1。

Input

第一行是一个整数 $T$，表示测试数据的组数。（$1 \leq T \leq 500$）

接下来每组测试数据包含两行：

• 第一行包含两个整数 $N$ 和 $D$，分别表示房子的数量和最大跳跃距离。（$1 \leq N \leq 1000$, $1 \leq D \leq 10^6$）
• 第二行包含 $N$ 个互不相同的整数，表示每栋房子的高度 $h_i$（$1 \leq h_i \leq 1000$），顺序为它们原本的排列顺序。

Output

对于每组测试数据，输出一行结果。

每组数据的输出格式为 "Case d: "，其中 $d$ 是当前测试数据的编号（从 1 开始），后接一个整数，表示最矮和最高房子之间可能达到的最大水平距离。如果无法满足题意条件，输出 -1。

Example

Sample Input

3
4 4 
20 30 10 40 
5 6 
20 34 54 10 15 
4 2 
10 20 16 13 

Sample Output

Case 1: 3
Case 2: 3
Case 3: -1