gSnake (Small)

Alex likes the Snake game.

The Google Doodle in the picture does not follow the exact rules described below. It only shows what this kind of game looks like.

Alex has just learned to program and wants to build his own version of Snake with these rules.

• The board has $R$ rows and $C$ columns. The top left cell is $(1, 1)$ and the bottom right cell is $(R, C)$.
• When the game starts, every cell $(r, c)$ with $r + c$ odd holds one piece of food. No other cell holds food.
• The body of the snake is an ordered sequence of one or more cells of the board. The first cell of the sequence is the head. The second cell, if there is one, shares an edge with the first cell, not only a corner, and the rest of the sequence continues the same way. The last cell of the sequence is the tail.
• The head always faces one of four directions: left, up, right, or down.
• When the game starts, the snake is on cell $(1, 1)$ and has length one, so the snake is only a head, and the head faces right.
• At every integer second (1 second, 2 seconds, and so on) the head moves into the neighbouring cell it faces. The board is cyclic, so a move off an edge brings the head back on the opposite edge. For example, a head at $(1, C)$ facing right moves to $(1, 1)$, and a head at $(1, C)$ facing up 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 the cell the head just left, the third cell moves to the cell the second cell just left, and the rest of the body follows the same way.
• When the head moves into a cell that holds food, the snake eats that food, so the cell no longer holds it, and the body grows. A new head appears on the cell the food was on, the old head becomes the second cell, the old second cell, if there was one, becomes the third cell, and the rest of the body follows the same way.
• If the head is on the same cell as another cell of the snake once a move is complete, the snake dies and the game ends immediately. If the head moves toward the cell the tail is on, the game does not end, because the tail leaves that cell before the move is complete.
• The player can make the snake turn. Action $A_i$ happens between second $X_i$ and second $X_i + 1$, and it is either L or R. An L action turns the head 90 degrees to the left, so a head that was facing down now faces right. An R action turns the head 90 degrees to the right, so a head that was facing down now faces left.
• The game has a time limit. If the game lasts that long, it ends once the move on second $10^9$ is complete.

Alex wrote down a series of turn actions to test the game. Simulate that series and report the length of the snake when the game is over. The game ends either because the head and another cell of the body are on the same cell once a move is complete, or because time runs out. In the first case, count the head and the body cell it overlaps as two separate cells when you measure the length.

The first line holds the number of test cases $T$. $T$ test cases follow. Each test case starts with three integers $S$, $R$, and $C$, where $S$ is the number of turn actions and $R$ and $C$ are the number of rows and columns of the board. $S$ lines follow. The $i$-th of them holds an integer $X_i$ and then a character $A_i$, which is either L or R, and it describes the action performed between second $X_i$ and second $X_i + 1$. The actions are given in increasing order of time, and no two actions happen between the same pair of seconds. The game may end before the snake performs all of them.

Limits

• $1 \le T \le 10$
• $1 \le R, C \le 100$
• $1 \le S \le 100$
• $1 \le X_i \le 2000$

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.