뱀 게임 시뮬레이션

알렉스는 뱀 게임을 좋아한다. 프로그래밍을 막 배운 알렉스는 다음 규칙을 따르는 자기만의 뱀 게임을 만들려고 한다.

• 게임판은 $R$행 $C$열이다. 왼쪽 위 칸의 좌표는 $(1, 1)$이고 오른쪽 아래 칸의 좌표는 $(R, C)$이다.
• 게임을 시작할 때 $r + c$가 홀수인 모든 칸 $(r, c)$에 먹이가 하나씩 놓여 있다. 나머지 칸에는 먹이가 없다.
• 뱀의 몸은 항상 서로 이어진 한 칸 이상의 칸을 순서대로 늘어놓은 것이다. 첫 번째 칸을 머리라고 부른다. 두 번째 칸이 있다면 첫 번째 칸과 변을 맞대고 있고(꼭짓점만 맞닿은 경우는 아니다), 그다음 칸도 같은 방식으로 이어진다. 마지막 칸을 꼬리라고 부른다.
• 뱀의 머리는 항상 왼쪽, 위쪽, 오른쪽, 아래쪽 중 한 방향을 보고 있다.
• 게임을 시작할 때 뱀은 칸 $(1, 1)$에 있고 길이는 1이다. 즉 머리만 있다. 머리는 오른쪽을 보고 있다.
• 정수 시각마다(1초, 2초, ...) 머리는 보고 있는 방향으로 한 칸 이동한다. 게임판은 순환한다. 판 밖으로 나가려고 하면 반대쪽 끝에서 나온다. 예를 들어 뱀이 $(1, C)$에 있고 머리가 오른쪽을 보고 있으면 머리는 $(1, 1)$로 이동한다. $(1, C)$에 있고 머리가 위쪽을 보고 있으면 머리는 $(R, C)$로 이동한다.
• 머리가 먹이 없는 칸으로 이동하면 뱀은 자라지 않는다. 두 번째 칸이 있으면 머리가 있던 자리로 이동하고, 세 번째 칸이 있으면 두 번째 칸이 있던 자리로 이동하며, 나머지 칸도 같은 방식으로 이동한다.
• 머리가 먹이가 있는 칸으로 이동하면 그 먹이를 먹고(그 칸에는 더 이상 먹이가 없다) 몸이 자란다. 먹이가 있던 칸에 새 머리가 생기고, 머리였던 칸이 두 번째 칸이 되고, 두 번째 칸이었던 칸이 세 번째 칸이 되며, 나머지 칸도 같은 방식으로 밀린다.
• 이동이 끝난 뒤 머리가 자기 몸의 다른 칸과 같은 자리에 있으면 뱀은 죽고 게임이 즉시 끝난다. 머리가 꼬리가 있던 칸으로 이동하는 경우에는 이동이 끝나기 전에 꼬리가 비켜나므로 게임이 끝나지 않는다.
• 플레이어는 뱀에게 회전 명령을 내릴 수 있다. $i$번째 명령 $A_i$는 $X_i$초와 $X_i + 1$초 사이에 일어난다. 명령은 "L"과 "R" 두 가지다. "L"은 머리를 왼쪽으로 90도 돌린다. 예를 들어 머리가 아래쪽을 보고 있었다면 오른쪽을 보게 된다. "R"은 머리를 오른쪽으로 90도 돌린다. 예를 들어 머리가 아래쪽을 보고 있었다면 왼쪽을 보게 된다.
• 게임에는 제한 시간이 있다. $10^9$초의 이동이 끝나면 게임이 끝난다.

알렉스가 적어 둔 회전 명령 목록을 그대로 시뮬레이션해서 게임이 끝났을 때 뱀의 길이를 구하라. 게임은 이동이 끝난 뒤 머리가 몸의 다른 칸과 겹쳐서 끝나거나, 제한 시간이 지나서 끝난다. 앞의 경우에는 겹친 머리와 몸의 칸을 서로 다른 두 칸으로 세어서 길이를 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $S$, $R$, $C$가 주어진다. $S$는 회전 명령의 개수이고, $R$과 $C$는 게임판의 행과 열의 개수이다. 다음 $S$개의 줄 중 $i$번째 줄에는 정수 $X_i$와 문자 $A_i$가 주어지며, $A_i$는 L 또는 R이다. 이 줄은 $X_i$초와 $X_i + 1$초 사이에 명령 $A_i$를 수행한다는 뜻이다.

명령은 시각이 커지는 순서로 주어지고, 같은 두 초 사이에 명령이 둘 이상 주어지는 일은 없다. 뱀이 명령을 모두 수행하기 전에 게임이 끝날 수도 있다.

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다. $y$는 게임이 끝났을 때 뱀의 길이이다.