题目描述

你是一个研究岛屿海岸气候的团队成员。该岛屿的海岸被建模为一个周长为 $K$ 公里的圆。海岸上有一座灯塔，占据圆周上的一个点。海岸上的每个点都被映射到 $[0, K)$ 范围内的一个实数；形式上，点 $x$ 表示从灯塔出发沿顺时针方向行走 $x$ 公里后到达的海岸点。例如，若 $K = 5$，点 $0$ 是灯塔所在位置，点 $1.5$ 是从灯塔出发顺时针方向 $1.5$ 公里的点，而点 $2.5$ 是灯塔的直径对称点。

你负责研究海岸温度。另一个团队安装了一套海岸温度测量系统，其工作原理如下：在特定位置部署了若干温度计以测量这些点的温度。没有两个温度计被放置在同一个点。在该团队的模型中，没有温度计的点被认为与最近温度计测量的温度相同。对于与两个温度计等距的点，使用顺时针方向的温度计（即从该点出发顺时针行走时最先遇到的温度计）。

遗憾的是，你不知道系统使用了多少个温度计或它们的具体位置，但你可以访问系统的温度数据。数据以两个长度为 $N$ 的列表给出：$X_1, X_2, \dots, X_N$ 和 $T_1, T_2, \dots, T_N$，表示对于每个 $1 \leq i < N$，满足 $X_i \leq x < X_{i+1}$ 的点 $x$ 被分配温度 $T_i$，而满足 $0 \leq x < X_1$ 或 $X_N \leq x < K$ 的点 $x$ 被分配温度 $T_N$。这些点按顺时针方向排列，因此对所有 $i$ 有 $X_i < X_{i+1}$。

你需要确定能够产生观测数据的最小温度计数量。

输入格式

输入的第一行包含测试用例的数量 $T$。随后是 $T$ 个测试用例；每个测试用例包含三行。第一行包含两个整数 $K$ 和 $N$：岛屿的周长和表示温度数据的列表大小。第二行包含 $N$ 个整数 $X_1, X_2, \dots, X_N$。第三行包含 $N$ 个整数 $T_1, T_2, \dots, T_N$。第二行和第三行的整数表示温度的方式如上所述。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是能够产生输入数据的最小温度计数量。

输入输出样例 #1

输入 #1

3
2 2
0 1
184 330
3 2
0 1
184 330
10 3
1 5 9
184 200 330

输出 #1

Case #1: 2
Case #2: 3
Case #3: 3

说明/提示

样例解释

在样例 #1 中，至少需要 2 个温度计，因为测量到了两种不同的温度。可以通过在点 0.5 放置一个温度计（测量值为 184）和在点 1.5 放置另一个温度计（测量值为 330）来生成数据。注意，点 0 和点 1 与两个温度计的距离相等，因此使用顺时针方向的温度计。点 0 的温度来自点 0.5 的温度计，点 1 的温度来自点 1.5 的温度计。

样例 #2 的数据无法仅用 2 个温度计生成。可以通过在点 0.2、点 1.8 和点 2.8 分别放置测量值为 184、330 和 330 的 3 个温度计来生成数据。还有其他放置 3 个温度计的方式也能生成输入数据。

在样例 #3 中，一种生成数据的方式是在点 0、点 2 和点 8 分别放置测量值为 330、184 和 200 的 3 个温度计。

数据范围

• $1 \leq T \leq 100$。
• $2 \leq N \leq \min(100, K)$。
• $0 \leq X_1$。
• 对所有 $i$，$X_i < X_{i+1}$。
• $X_N < K$。
• 对所有 $i$，$184 \leq T_i \leq 330$。
• 对所有 $i$，$T_i \neq T_{i+1}$。
• $T_1 \neq T_N$。

测试集 1（5 分，可见判定）

• $2 \leq K \leq 10$。

测试集 2（19 分，隐藏判定）

• $2 \leq K \leq 10^9$。