gSnake (작은 데이터)

알렉스는 스네이크 게임을 좋아한다.

그림의 구글 두들은 아래에서 설명하는 규칙과 정확히 같지 않다. 이런 게임이 어떻게 생겼는지 보여 줄 뿐이다.

이제 막 프로그래밍을 배운 알렉스는 다음 규칙을 따르는 자기만의 스네이크를 만들려고 한다.

• 판은 $R$행 $C$열이다. 왼쪽 위 칸의 좌표는 $(1, 1)$, 오른쪽 아래 칸의 좌표는 $(R, C)$이다.
• 게임이 시작할 때 $r + c$가 홀수인 모든 칸 $(r, c)$에 먹이가 하나씩 놓여 있다. 나머지 칸에는 먹이가 없다.
• 뱀의 몸은 판 위의 칸을 순서대로 늘어놓은 것이고, 칸은 하나 이상이다. 수열의 첫 칸을 머리라고 한다. 두 번째 칸이 있다면 첫 칸과 변을 맞대고 있고, 꼭짓점만 닿아서는 안 되며, 그 뒤도 같은 방식으로 이어진다. 수열의 마지막 칸을 꼬리라고 한다.
• 머리는 항상 왼쪽, 위, 오른쪽, 아래 중 한 방향을 바라본다.
• 게임이 시작할 때 뱀은 칸 $(1, 1)$에 있고 길이는 1이라서 머리만 있으며, 머리는 오른쪽을 바라본다.
• 정수 초마다, 즉 1초, 2초와 같은 시각마다 머리는 바라보는 방향의 이웃 칸으로 이동한다. 판은 순환하므로 가장자리 밖으로 나가면 반대쪽 가장자리에 다시 나타난다. 예를 들어 $(1, C)$에서 오른쪽을 보는 머리는 $(1, 1)$로 이동하고, $(1, C)$에서 위를 보는 머리는 $(R, C)$로 이동한다.
• 머리가 먹이 없는 칸으로 이동하면 뱀은 자라지 않는다. 두 번째 칸이 있다면 머리가 방금 떠난 칸으로 옮겨 가고, 세 번째 칸은 두 번째 칸이 방금 떠난 칸으로 옮겨 가며, 나머지 몸도 같은 방식으로 따라간다.
• 머리가 먹이가 있는 칸으로 이동하면 그 먹이를 먹어서 그 칸에는 먹이가 없어지고, 몸이 자란다. 먹이가 있던 칸에 새 머리가 생기고, 머리였던 칸은 두 번째 칸이 되며, 두 번째 칸이 있었다면 세 번째 칸이 되고, 나머지 몸도 같은 방식으로 밀린다.
• 이동이 끝난 뒤 머리가 뱀의 다른 칸과 같은 자리에 있으면 뱀은 죽고 게임이 즉시 끝난다. 머리가 꼬리가 있는 칸 쪽으로 이동할 때는 이동이 끝나기 전에 꼬리가 그 칸을 떠나므로 게임이 끝나지 않는다.
• 플레이어는 뱀에게 회전 동작을 시킬 수 있다. 동작 $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$초 사이에 하는 동작을 나타낸다. 동작은 시간 순서대로 주어지며, 같은 두 초 사이에 동작이 둘 이상 오지 않는다. 뱀이 동작을 모두 하기 전에 게임이 끝날 수도 있다.

제한

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

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