Problem Description

Ada has decided that this year, she will take part in the annual marathon that takes place in her city. Since this is the first time she would be running such a long distance, she has decided to start practising for it by running in the circular track of length $L$ units near her house.

Ada wants to focus only on running, so she decides to use a machine to count the number of laps she has run. The machine is placed at the starting line of the circular track and starts the count from $0$. Every time Ada arrives at the starting line running in the same direction as the last time she departed from the starting line, the machine increases the number of laps that Ada has run by $1$. If she crosses the starting line or changes direction at the starting line, the machine considers the new direction as the direction she last touched the starting line. The machine only remembers the last direction in which Ada touched the starting line. During a lap, Ada can change directions any number of times, but as long as she eventually touches the starting line in the same direction as she last touched it, the count of laps in the machine increases by $1$.

This is the first time Ada has practised running long distances, so she cannot run continuously. She runs some distance, then takes a break to regain her energy. However, when she starts running again after taking a break, she cannot remember which direction she was running in previously. So she picks one of the directions, clockwise or anticlockwise, and starts running from the same position where she stopped.

Ada begins at the starting line and is initially facing in the direction of her first run. She runs a total of $N$ times, taking breaks in between. Given the information of the distance $D_i$ units Ada has run, and the direction $C_i$ she has taken (clockwise or anticlockwise) when she ran the $i$-th time, for all $i$ from $1, \ldots, N$, can you tell the number of laps that would be reported by the machine at the end?

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two positive integers $L$ and $N$, the length of the circular track in units, and the number of times Ada has run respectively.

The next $N$ lines describe Ada's runs. The $i$-th line contains a positive integer $D_i$ and a character $C_i$, the distance in units Ada has run and the direction she has taken (clockwise or anticlockwise) respectively during the $i$-th run. $C_i$ will always be either 'C' (denoting clockwise direction) or 'A' (denoting anticlockwise direction).

Output Format

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is a non negative integer denoting the number of laps reported by the machine at the end.

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

Hint

In Sample Case #$1$, the length of the circular track is $5$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs $8$ units in the clockwise direction, touching the starting line in the process, and the number of laps in the machine increases by $1$. The machine now reports $1$ lap. Ada is now $3$ units from the starting line in the clockwise direction.
• Next, she runs $3$ units in the clockwise direction. This time, she touches the starting line again and the number of laps in the machine increase by $1$. The machine now reports $2$ laps. After this, she is $1$ unit from the starting line in the clockwise direction.
• Finally, she runs $6$ units in the clockwise direction, and she touches the starting line again, increasing the number of laps in the machine by $1$. At the end, the machine reports $3$ laps.

In Sample Case #$2$, the length of the circular track is $8$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs $5$ units in the clockwise direction. Ada is now $5$ units from the starting line in the clockwise direction.
• Next, she runs $9$ units in the clockwise direction, touching the starting line. The number of laps in the machine increases by $1$. The machine now reports $1$ lap. After this, she is $6$ units from the starting line in the clockwise direction.
• Next, she runs $8$ units in the clockwise direction. She touches the starting line again, increasing the number of laps in the machine by $1$. The machine now reports $2$ laps. After this, she is $6$ units from the starting line in the clockwise direction.
• Finally, she runs $20$ units in the clockwise direction. This time, she touches the starting line a total of $3$ times, increasing the number of laps in the machine by $3$. At the end, the machine reports $5$ laps.

In Additional Sample Case #$1$, the length of the circular track is $5$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs $8$ units in the clockwise direction, touching the starting line in the process, and the number of laps in the machine increases by $1$. The machine now reports $1$ lap. Ada is now $3$ units from the starting line in the clockwise direction.
• Next, she runs runs $4$ units in the anticlockwise direction. She touches the starting line, but since she touches it running in the opposite direction to what she was running previously, this does not increase the number of laps in the machine. She is now $1$ unit from the starting line in the anticlockwise direction.
• Finally, she runs $5$ units in the clockwise direction. This time, again, she touches the starting line, but since she last touched it in the anticlockwise direction, this is not counted by the machine. She does not touch the starting line again and at the end, the machine reports $1$ lap.

In Additional Sample Case #$2$, the length of the circular track is $4$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs $2$ units in the clockwise direction. Ada is now $2$ units from the starting line in the clockwise direction.
• Next, she runs runs $8$ units in the anticlockwise direction. She touches the starting line, but since she touches it running in the opposite direction to what she was running previously, this does not increase the number of laps in the machine. She then continues running and ends up touching the starting line again. This time the number of laps reported by the machine increases by $1$. The machine now reports $1$ lap. After this run, she is $2$ units from the starting line in the anticlockwise direction.
• Next, she runs $3$ units in the anticlockwise direction. She touches the starting line, and the number of laps in the machine increases by $1$. The machine now reports $2$ laps. After this run, she is $1$ unit from the starting line in the anticlockwise direction.
• Next, she runs $5$ units in the clockwise direction. She touches the starting line, but this is not counted by the machine. She keeps running and then touches the starting line at the end of her run, increasing the number of laps in the machine by $1$. The machine now reports $3$ laps. After this run, she is at the starting line facing the clockwise direction.
• Finally, she runs $8$ units in the anticlockwise direction. At the beginning of this run, she changes her direction at the starting line, and the machine now considers the new direction, anticlockwise, as the direction she last touched the starting line. She continues running and touches the starting line twice in the anticlockwise direction, increasing the number of laps in the machine by $2$. At the end, the machine reports $5$ laps.

In Additional Sample Case #$3$, the length of the circular track is $4$ units. Ada is facing in the clockwise direction in the beginning.

• First, Ada runs $3$ units in the clockwise direction. After this, she is $3$ units from the starting line in the clockwise direction.
• Next, she runs $2$ units in the anticlockwise direction. During this run, she does not touch the starting line, so the machine still considers the clockwise direction as the last direction. After this run, she is $1$ unit from the starting line in the clockwise direction.
• Finally, she runs $5$ units in the clockwise direction. She crosses the starting line once, running in the same direction, clockwise, as the last time she departed from it and the count of number of laps in the machine increases by $1$. At the end, the machine reports $1$ lap.

Limits

$1 \le T \le 100$.

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

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

$1 \le D_i \le 10^9$, for all $1 \le i \le N$.

Test Set $1$

$C_i$ is always 'C', for all $1 \le i \le N$.

Test Set $2$

$C_i$ can be either 'C' or 'A', for all $1 \le i \le N$.