1060. 墙的重建

Blotch修建了一面墙。

墙由 $N$ 个部分构成,从左到右依次编号 $1$ 到 $N$。

由于他修建的十分匆忙,墙的各个部分高度可能并不相同。

第 $i$ 个部分墙体的高度用 $A_i$ 来表示。

Blotch想要通过重建部分墙面,从而对墙进行修整。

他可以将任意部分的墙面重修为任意高度。

重修完成之后,如果满足 $A_i \neq A_{i+1}$ 的 $i \ (1 \le i < N)$ 的数量不超过 $k$,他将会十分高兴。

在满足能够使得Blotch十分高兴的前提下,最少需要重建多少部分墙面?

输入格式

第一行包含整数 $T$,表示共有 $T$ 组测试数据。

每组测试数据共两行,第一行包含整数 $N$ 和 $k$。

第二行包含 $N$ 个整数,其中第 $i$ 个整数表示第 $i$ 部分墙体的高度 $A_i$。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为最少需要重建的墙面数量。

数据范围

$1 \le T \le 100$,
$1 \le A_i \le 1000$,
$0 \le k \le N$,
$2 \le N \le 100$

输入样例:

4
8 2
300 100 300 300 200 100 800 500
5 3
100 100 100 100 3
7 3
10 20 40 10 10 30 30
10 2
30 30 60 60 90 90 60 60 30 30

输出样例:

Case #1: 3
Case #2: 0
Case #3: 1
Case #4: 2

样例解释

在第一个示例中,有N = 8个墙段,如果相邻段之间的高度变化最多为K = 2,则Blotch会很高兴。他可以:

  • 重建墙壁的第二部分,使其高度为300,
  • 重建墙壁的第六部分,使其高度为200,
  • 重建墙壁的第八部分,使其高度为800。

这将产生一面各部分高度分别为300、300、300、300、200、200、800、800的墙,这使Blotch感到高兴。

在第二个示例中,有N = 5个墙段,并且如果相邻段之间的高度变化最多为K = 3,则Blotch将很高兴。 Blotch已经对这堵墙感到满意,因此他不需要重建任何部分。

在第三个示例中,有N = 7个墙段,并且如果相邻段之间的高度变化最多为K = 3,则Blotch将很高兴。他可以:

  • 重建墙的第二部分,使其高度为10。

这将产生一面各部分高度分别为10、10、40、10、10、30、30的墙,这使Blotch感到高兴。

在第四个示例中,有N = 10个墙段,并且如果相邻段之间的高度变化最多为K = 2,则Blotch将很高兴。他可以:

  • 重建墙壁的第五部分,使其高度为60,
  • 重建墙壁的第六部分,使其高度为60。

这将产生一面各部分高度分别为30、30、60、60、60、60、60、60、60、30、30的墙,这使Blotch感到高兴。