뱀 게임 시뮬레이션

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

게임판은 $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$ 를 수행한다는 뜻이다.

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

뱀 게임 시뮬레이션

문제

입력

제한

출력