SCENARIO

Ramya 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.

Ramya 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 Ramya 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 Ramya 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 Ramya touched the starting line. During a lap, Ramya 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.

Since it's been long since Ramya has practised running long distances, 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.

Ramya 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 Di units Ramya has run, and the direction Ci she has taken (clockwise or anticlockwise) when she ran the i-th time, for all i from 1,…,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 Ramya has run respectively.

• The next N lines describe Ramya's runs.

• The i-th line contains a positive integer Di and a character Ci, the distance in units Ramya has run and the direction she has taken (clockwise or anticlockwise) respectively during the i-th run.

• Ci 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.

Limits

1≤T≤100.
1≤L≤10^9.
1≤N≤10^4.
1≤Di≤10^9, 
for all 1≤i≤N.

Sample Input:

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

Sample Output

Case #1: 1
Case #2: 5

Explanation:

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

• First, Ramya 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. Ramya 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 Sample Case #2, the length of the circular track is 4 units. Ramya is facing the clockwise direction in the beginning.

• First, Ramya runs 2 units in the clockwise direction. Ramya 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.