你是研究岛屿海岸气候的研究团队的一员。岛屿的海岸被建模为一个周长为 $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 \le i < N$，点 $x$（其中 $X_i \le x < X_{i+1}$）被分配温度 $T_i$，且对于 $0 \le x < X_1$ 或 $X_N \le 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$ 是能够产生所观察到的输入数据的最少温度计数量。

数据范围

时间限制：30 秒。 内存限制：1 GB。 $1 \le T \le 100$。 $2 \le N \le \min(100, K)$。 $0 \le X_1$。 对于所有 $i$，$X_i < X_{i+1}$。 $X_N < K$。 对于所有 $i$，$184 \le T_i \le 330$。 对于所有 $i$，$T_i \neq T_{i+1}$。 $T_1 \neq T_N$。

样例

样例输入 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 个温度计，因为测量到了两种不同的温度。使用恰好 2 个温度计是可以产生该数据的，一个温度计（测量值为 184）位于点 0.5，另一个（测量值为 330）位于点 1.5。注意，点 0 和点 1 与两个温度计的距离相等，因此使用顺时针方向的温度计。点 0 测得的温度来自位于 0.5 的温度计，点 1 测得的温度来自位于 1.5 的温度计。

样例 2 中的数据无法仅用 2 个温度计产生。如果将 3 个温度计分别放置在点 0.2、点 1.8 和点 2.8，测量值分别为 184、330 和 330，则可以产生该数据。还有其他放置 3 个温度计的方法也能产生相同的输入数据。

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