题目描述

Ada 决定今年参加她所在城市的年度马拉松。由于这是她第一次跑这么长的距离，她决定在离家不远的一条长度为 $L$ 单位的圆形跑道上练习跑步。

Ada 只想专注于跑步，因此她决定使用一台机器来记录她跑了多少圈。机器放置在跑道的起点线上，并从 $0$ 开始计数。每当 Ada 以与上次离开起点线时相同的方向到达起点线时，机器就会将她跑的圈数增加 $1$。如果她越过起点线或在起点线处改变方向，机器会将新方向视为她上次接触起点线时的方向。机器只记住 Ada 最后一次接触起点线时的方向。在一圈中，Ada 可以任意多次改变方向，但只要她最终以与上次接触起点线时相同的方向接触起点线，机器中的圈数就会增加 $1$。

这是 Ada 第一次练习长跑，所以她无法持续奔跑。她跑一段距离，然后休息以恢复体力。然而，当她休息后再次开始跑步时，她记不清之前跑的方向。于是她选择顺时针或逆时针方向之一，并从她停下的位置开始奔跑。

Ada 从起点线出发，最初面朝她第一次跑步的方向。她总共跑了 $N$ 次，中间有休息。给定 Ada 第 $i$ 次跑步的距离 $D_i$ 单位以及她所选择的方向 $C_i$（顺时针或逆时针），对于所有 $i = 1, \ldots, N$，你能说出最终机器报告的圈数吗？

输入格式

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

每个测试用例的第一行包含两个正整数 $L$ 和 $N$，分别表示圆形跑道的长度（单位）和 Ada 跑步的次数。

接下来的 $N$ 行描述 Ada 的每次跑步。第 $i$ 行包含一个正整数 $D_i$ 和一个字符 $C_i$，分别表示 Ada 第 $i$ 次跑步的距离（单位）和所选择的方向（顺时针或逆时针）。$C_i$ 始终为 'C'（表示顺时针）或 'A'（表示逆时针）。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个非负整数，表示最终机器报告的圈数。

2
5 3
8 C
3 C
6 C
8 4
5 C
9 C
8 C
20 C

Case #1: 3
Case #2: 5

3
5 3
8 C
4 A
5 C
4 5
2 C
8 A
3 A
5 C
8 A
4 3
3 C
2 A
5 C

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

提示

在样例 #1 中，圆形跑道的长度为 $5$ 单位。Ada 最初面朝顺时针方向。

• 首先，Ada 顺时针跑 $8$ 单位，过程中接触到了起点线，机器中的圈数增加 $1$。机器现在报告 $1$ 圈。Ada 现在位于起点线顺时针方向 $3$ 单位处。
• 接着，她顺时针跑 $3$ 单位。这次她又接触到了起点线，机器中的圈数增加 $1$。机器现在报告 $2$ 圈。之后，她位于起点线顺时针方向 $1$ 单位处。
• 最后，她顺时针跑 $6$ 单位，再次接触起点线，机器中的圈数增加 $1$。最终机器报告 $3$ 圈。

在样例 #2 中，圆形跑道的长度为 $8$ 单位。Ada 最初面朝顺时针方向。

• 首先，Ada 顺时针跑 $5$ 单位。她位于起点线顺时针方向 $5$ 单位处。
• 接着，她顺时针跑 $9$ 单位，接触到起点线。机器中的圈数增加 $1$。机器现在报告 $1$ 圈。之后，她位于起点线顺时针方向 $6$ 单位处。
• 接着，她顺时针跑 $8$ 单位，再次接触起点线，机器中的圈数增加 $1$。机器现在报告 $2$ 圈。之后，她位于起点线顺时针方向 $6$ 单位处。
• 最后，她顺时针跑 $20$ 单位。这次她总共接触起点线 $3$ 次，机器中的圈数增加 $3$。最终机器报告 $5$ 圈。

在附加样例 #1 中，圆形跑道的长度为 $5$ 单位。Ada 最初面朝顺时针方向。

• 首先，Ada 顺时针跑 $8$ 单位，过程中接触到了起点线，机器中的圈数增加 $1$。机器现在报告 $1$ 圈。Ada 现在位于起点线顺时针方向 $3$ 单位处。
• 接着，她逆时针跑 $4$ 单位。她接触到了起点线，但由于她是以与之前跑步相反的方向接触，这不会增加机器中的圈数。她现在位于起点线逆时针方向 $1$ 单位处。
• 最后，她顺时针跑 $5$ 单位。这次她又接触到了起点线，但由于她上次接触时是逆时针方向，所以这次不被机器计入。她没有再接触起点线，最终机器报告 $1$ 圈。

在附加样例 #2 中，圆形跑道的长度为 $4$ 单位。Ada 最初面朝顺时针方向。

• 首先，Ada 顺时针跑 $2$ 单位。她位于起点线顺时针方向 $2$ 单位处。
• 接着，她逆时针跑 $8$ 单位。她接触到了起点线，但由于她是以与之前跑步相反的方向接触，这不会增加机器中的圈数。她继续奔跑，最终再次接触到起点线。这次机器报告的圈数增加 $1$。机器现在报告 $1$ 圈。这次跑步结束后，她位于起点线逆时针方向 $2$ 单位处。
• 接着，她逆时针跑 $3$ 单位。她接触到了起点线，机器中的圈数增加 $1$。机器现在报告 $2$ 圈。之后，她位于起点线逆时针方向 $1$ 单位处。
• 接着，她顺时针跑 $5$ 单位。她接触到了起点线，但这次不被机器计入。她继续奔跑，然后在跑步结束时再次接触起点线，机器中的圈数增加 $1$。机器现在报告 $3$ 圈。这次跑步结束后，她位于起点线处，面朝顺时针方向。
• 最后，她逆时针跑 $8$ 单位。在这次跑步开始时，她在起点线处改变了方向，机器现在将新方向（逆时针）视为她上次接触起点线的方向。她继续奔跑，并逆时针方向两次接触起点线，机器中的圈数增加 $2$。最终机器报告 $5$ 圈。

在附加样例 #3 中，圆形跑道的长度为 $4$ 单位。Ada 最初面朝顺时针方向。

• 首先，Ada 顺时针跑 $3$ 单位。之后，她位于起点线顺时针方向 $3$ 单位处。
• 接着，她逆时针跑 $2$ 单位。在这次跑步中，她没有接触起点线，因此机器仍将顺时针方向视为最后一次方向。这次跑步结束后，她位于起点线顺时针方向 $1$ 单位处。
• 最后，她顺时针跑 $5$ 单位。她越过起点线一次，以与上次离开时相同的方向（顺时针）奔跑，机器中的圈数增加 $1$。最终机器报告 $1$ 圈。

限制条件

$1 \le T \le 100$。

$1 \le L \le 10^9$。

$1 \le N \le 10^4$。

对于所有 $1 \le i \le N$，$1 \le D_i \le 10^9$。

测试集 1

对于所有 $1 \le i \le N$，$C_i$ 始终为 'C'。

测试集 2

对于所有 $1 \le i \le N$，$C_i$ 可以是 'C' 或 'A'。

翻译由 DeepSeek V4 Pro 完成