원형 트랙 달리기

Ada는 올해 도시에서 열리는 연례 마라톤에 참가하기로 했다. 이렇게 긴 거리를 달려 본 적이 없어서, 집 근처에 있는 길이 $L$ 단위의 원형 트랙에서 연습하기로 했다.

Ada는 달리기에만 집중하고 싶어서 기계로 달린 바퀴 수를 센다. 기계는 출발선에 놓여 있고 0부터 센다. Ada가 마지막으로 출발선을 떠났을 때와 같은 방향으로 출발선에 도착할 때마다 기계는 바퀴 수를 1 늘린다. Ada가 출발선을 지나거나 출발선에서 방향을 바꾸면, 기계는 그 새 방향을 Ada가 마지막으로 출발선을 밟은 방향으로 본다. 기계가 기억하는 것은 Ada가 마지막으로 출발선을 밟은 방향뿐이다. 한 바퀴를 도는 동안 Ada는 원하는 만큼 방향을 바꿀 수 있지만, 결국 마지막으로 밟았던 방향과 같은 방향으로 출발선을 밟으면 기계의 바퀴 수가 1 늘어난다.

Ada는 긴 거리를 연달아 달리지 못해서, 조금 달린 뒤 쉬면서 체력을 회복한다. 쉬고 다시 달릴 때에는 이전에 어느 방향으로 달리고 있었는지 기억하지 못한다. 그래서 시계 방향이나 반시계 방향 중 하나를 골라, 멈춘 자리에서 그대로 달리기 시작한다.

Ada는 출발선에서 시작하며, 처음 달리는 방향을 향하고 있다. 쉬는 시간을 사이에 두고 총 $N$번 달린다. $i$번째 달리기에서 Ada가 달린 거리 $D_i$ 단위와 선택한 방향 $C_i$(시계 방향 또는 반시계 방향)가 주어질 때, 마지막에 기계가 보고하는 바퀴 수를 구하라.

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

각 테스트 케이스의 첫 줄에는 원형 트랙의 길이 $L$ 단위와 Ada가 달린 횟수 $N$을 나타내는 양의 정수 두 개가 주어진다.

다음 $N$개의 줄은 Ada의 달리기를 나타낸다. $i$번째 줄에는 $i$번째 달리기에서 달린 거리를 나타내는 양의 정수 $D_i$와 선택한 방향을 나타내는 문자 $C_i$가 주어진다. $C_i$는 항상 'C'(시계 방향) 또는 'A'(반시계 방향)이다.

각 테스트 케이스마다 한 줄에 Case #x: y를 출력한다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 마지막에 기계가 보고하는 바퀴 수인 0 이상의 정수이다.

$1 \le T \le 100$.

$1 \le L \le 10^9$.

$1 \le N \le 10^4$.

$1 \le D_i \le 10^9$ (모든 $1 \le i \le N$에 대해).