题目描述

Blotch 砌了一面墙。这面墙由 $N$ 段组成，从左到右编号为 $1$ 到 $N$。由于他当时匆忙砌墙，并非所有段的高度都相同。第 $i$ 段墙的高度为 $A_i$ 米。

Blotch 希望通过重建其中的一些段来修复他的墙。他可以将每一段重建的高度设为任意他想要的高度。

如果满足 $A_i \ne A_{i+1}$ 的下标 $i$（$1 \le i < N$）的个数不超过 $K$，那么 Blotch 就会感到满意。

请问 Blotch 至少需要重建多少段墙，才能使他感到满意？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$，分别表示墙的段数和相邻段之间高度变化的最大允许次数。

第二行包含 $N$ 个整数。其中第 $i$ 个整数是 $A_i$，表示第 $i$ 段墙的高度。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Blotch 为了感到满意而需要重建的最少段数。

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 就会满意。他可以：

• 将第 $2$ 段重建为高度 $300$，
• 将第 $6$ 段重建为高度 $200$，
• 将第 $8$ 段重建为高度 $800$。

这样得到的高度序列为 $300, 300, 300, 300, 200, 200, 800, 800$，使 Blotch 感到满意。

在第二个样例中，墙有 $N = 5$ 段，Blotch 在相邻段高度变化不超过 $K = 3$ 时就会满意。他原本的墙已经满足条件，因此不需要重建任何段。

在第三个样例中，墙有 $N = 7$ 段，Blotch 在相邻段高度变化不超过 $K = 3$ 时就会满意。他可以：

• 将第 $2$ 段重建为高度 $10$。

得到的高度序列为 $10, 10, 40, 10, 10, 30, 30$，使 Blotch 感到满意。

在第四个样例中，墙有 $N = 10$ 段，Blotch 在相邻段高度变化不超过 $K = 2$ 时就会满意。他可以：

• 将第 $5$ 段重建为高度 $60$，
• 将第 $6$ 段重建为高度 $60$。

得到的高度序列为 $30, 30, 60, 60, 60, 60, 60, 60, 30, 30$，使 Blotch 感到满意。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le A_i \le 1000$。

$0 \le K \le N$。

测试集 1（可见）

$2 \le N \le 20$。

测试集 2（隐藏）

$2 \le N \le 100$。

翻译由 DeepSeek V4 Pro 完成