Snake Game Simulation

Alex likes the Snake game. He has just learned to program and wants to build his own version with the following rules.

• The board has $R$ rows and $C$ columns. The top left cell has coordinates $(1, 1)$ and the bottom right cell has coordinates $(R, C)$.
• At the start of the game, every cell $(r, c)$ with $r + c$ odd holds one piece of food. No other cell holds food.
• The snake's body is always an ordered, connected sequence of one or more cells. The first cell of the sequence is the head. The second cell, if there is one, shares an edge with the first cell (sharing only a corner does not count), and the rest of the sequence continues the same way. The last cell is the tail.
• The head always faces left, up, right, or down.
• At the start of the game the snake is at cell $(1, 1)$ and its length is 1, so it consists of the head alone. The head faces right.
• At each integer time (1 second, 2 seconds, and so on) the head moves one cell in the direction it faces. The board is cyclic, so moving off an edge brings the head back on the opposite edge. For example, if the snake is at $(1, C)$ and its head faces right, the head moves to $(1, 1)$. If the snake is at $(1, C)$ and its head faces up, the head moves to $(R, C)$.
• When the head moves into a cell with no food, the snake does not grow. The second cell, if there is one, moves to where the head was, the third cell, if there is one, moves to where the second cell was, and the rest move the same way.
• When the head moves into a cell with food, the snake eats the food (that cell no longer holds food) and grows. A new head appears in the cell that held the food, the old head becomes the second cell, the old second cell becomes the third cell, and the rest shift the same way.
• If, after a move is complete, the head is in the same place as another cell of the snake, the snake dies and the game ends immediately. If the head moves into the cell where the tail was, the game does not end, because the tail moves out of the way before the move is complete.
• The player can make the snake perform turn actions. Action $A_i$ happens between second $X_i$ and second $X_i + 1$. There are two actions, "L" and "R". "L" turns the head 90 degrees to the left, so a head that faced down now faces right. "R" turns the head 90 degrees to the right, so a head that faced down now faces left.
• The game has a time limit. It ends once the move on second $10^9$ is complete.

Simulate the list of turn actions Alex wrote down and report the length of the snake when the game is over. The game ends either because the head overlaps another cell of the snake after a move is complete, or because the time limit passes. In the first case, count the head and the overlapping body cell as two separate cells when measuring the length.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains three integers $S$, $R$, and $C$. $S$ is the number of turn actions, and $R$ and $C$ are the number of rows and columns of the board. Each of the next $S$ lines contains an integer $X_i$ and a character $A_i$, where $A_i$ is L or R. That line means action $A_i$ is performed between second $X_i$ and second $X_i + 1$.

The actions are given in increasing order of time, and there is never more than one action between the same two seconds. The game may end before the snake performs all of the actions.

• $1 \le T \le 10$
• $1 \le R, C \le 100000$
• $1 \le S \le 100000$
• $1 \le X_i \le 1000000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the length of the snake when the game is over.