题目描述

假设你有一个密码锁，它由 $N$ 个拨盘组成，初始时设置为随机组合。密码锁的拨盘大小为 $D$，即每个拨盘的值可以是 $0$ 到 $D-1$（包含两端），并且可以向上或向下旋转。拨盘从左到右排列，最左和最右的位置分别为 $1$ 和 $N$。将所有的拨盘值设为 $0$ 即可打开密码锁。

你可以执行零次或多次以下操作：

• 选择任意区间 $[l, r]$，满足 $1 \le l \le r \le N$，并将该区间内的所有拨盘同时向上或向下旋转。向上旋转会使区间 $[l, r]$ 中每个拨盘的值增加 $1$，向下旋转则减少 $1$。注意，值为 $D-1$ 的拨盘向上旋转后会变成 $0$，值为 $0$ 的拨盘向下旋转后会变成 $D-1$。

操作序列必须满足以下条件：

• 第 $i-1$ 次操作选择的区间 $[l_{i-1}, r_{i-1}]$ 必须完全包含在第 $i$ 次操作选择的区间 $[l_i, r_i]$ 之内，即 $l_i \le l_{i-1} \le r_{i-1} \le r_i$。第一次操作 $([l_1, r_1])$ 可以任意选择。

解锁初始组合为 $[1, 1, 2, 2, 3, 3]$ 的密码锁的有效操作序列示例：

1. 将区间 $[5, 6]$ 向下旋转。
2. 将区间 $[3, 6]$ 向下旋转。
3. 将区间 $[1, 6]$ 向下旋转。

以下是一些不能执行的操作：

1. 在 $[6, 9]$ 之后旋转 $[1, 4]$，因为 $[6, 9]$ 没有完全包含在 $[1, 4]$ 中（不满足 $r_{i-1} \le r_i$，其中 $r_{i-1}=9$，$r_i=4$）。
2. 在 $[2, 7]$ 之后旋转 $[3, 6]$。

你的目标是输出使密码锁所有拨盘归零所需的最少有效操作次数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例由 $2$ 行组成。

每个测试用例的第一行包含 $2$ 个整数 $N$ 和 $D$，分别表示密码锁的拨盘数量和拨盘的大小。

每个测试用例的第二行包含 $N$ 个整数 $V_1, V_2, \ldots, V_N$，其中第 $i$ 个整数表示初始组合中第 $i$ 个拨盘的值。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是解锁密码锁所需的最少操作次数。

2
6 2
1 1 0 1 0 1
6 2
0 1 0 0 1 1

Case #1: 3
Case #2: 2

2
6 10
1 1 2 2 3 3
6 10
1 1 9 9 1 1

Case #1: 3
Case #2: 3

提示

在样例 #1 中，解锁密码锁所需的最少操作次数为 $3$。可以使用以下操作解锁：

1. 将区间 $[4, 4]$ 向下旋转。
2. 将区间 $[3, 5]$ 向下旋转。
3. 将区间 $[1, 6]$ 向下旋转。

在样例 #2 中，解锁密码锁所需的最少操作次数为 $2$。可以使用以下操作解锁：

1. 将区间 $[3, 4]$ 向上旋转。
2. 将区间 $[2, 6]$ 向下旋转。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$0 \le V_i \le D - 1$。

测试集 1

$1 \le N \le 40$。

$D = 2$。

测试集 2

$1 \le N \le 40$。

$2 \le D \le 10$。

测试集 3

$1 \le N \le 400$。

$2 \le D \le 10^9$。

翻译由 DeepSeek V4 Pro 完成