주머니의 넓이 (작은 입력)

평면나라(Flatland)의 성실한 시민 폴리고노비치 교수는 평면의 격자점을 따라 산책하기를 좋아한다. 아침에 원점에서 출발해 북쪽을 바라보고 서며, 다음 세 가지 행동만 한다.

• 'F': 바라보는 방향으로 한 칸 전진한다.
• 'L': 왼쪽으로 90도 돈다.
• 'R': 오른쪽으로 90도 돈다.

하루가 끝날 때(그렇다, 아주 긴 산책이다) 교수는 원점으로 돌아온다. 원점을 빼면 같은 점을 두 번 지나지 않으므로, 산책 경로는 다각형 하나를 둘러싼다. 아래 그림에서 다각형의 내부는 파란색이다. 점 $x$, $y$, $z$, $w$는 잠시 뒤에 설명한다.

교수가 방향을 네 번보다 많이 틀면 이 다각형은 볼록하지 않다. 그래서 다각형에 주머니가 생긴다.

주의! 이 문제에서 말하는 주머니의 정의는 이미 알고 있는 정의와 다를 수 있다.

아래 그림에서 회색으로 칠한 부분이 다각형의 주머니다.

정확히 말해, 점 $p$가 주머니에 속한다는 것은 $p$가 다각형 내부의 점이 아니고 다음 두 조건 중 적어도 하나를 만족한다는 뜻이다.

• $p$의 정동쪽과 정서쪽에 모두 경계점이 있다.
• $p$의 정북쪽과 정남쪽에 모두 경계점이 있다.

경계점은 교수가 산책하며 지나간 점이다. 좌표가 정수인 점만이 아니라 지나간 선분 위의 모든 점을 포함한다.

첫 번째 그림을 다시 보자. 점 $x$는 첫 번째 조건을 만족하고, 점 $z$는 두 번째 조건을 만족하며, 점 $y$는 두 조건을 모두 만족한다. 세 점 모두 주머니에 속한다. 점 $w$는 주머니에 속하지 않는다.

교수의 산책이 주어지면 주머니 전체의 넓이를 구하라.

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

각 테스트 케이스는 산책 하나를 나타낸다. 먼저 정수 $L$이 주어지고, 그 뒤에 "$S$ $T$" 꼴의 쌍이 $L$개 이어진다. $S$는 'L', 'R', 'F'로 이루어진 문자열이고, $T$는 $S$를 몇 번 반복하는지 나타내는 정수다.

즉 한 테스트 케이스의 입력은 다음 모양이다.

S1 T1 S2 T2 ... SL TL

교수가 하는 행동은 $S_1$을 $T_1$번, 그다음 $S_2$를 $T_2$번, 이렇게 차례로 이어 붙인 것이다.

한 테스트 케이스의 쌍이 모두 같은 줄에 있지는 않을 수 있다. 다만 문자열 $S$ 하나가 여러 줄에 걸쳐 쪼개지는 일은 없다.

제한

• $1 \le N \le 100$
• $1 \le L \le 100$
• 각 문자열 $S$의 길이는 1 이상 16 이하다.
• $1 \le T$
• 이어 붙인 경로에는 방향 전환이 연속으로 두 번 나오지 않는다. 즉 'LL', 'RR', 'LR', 'RL'이 나타나지 않는다. 경로에는 'F'가 적어도 하나 있다.
• 경로는 마지막에 원점으로 돌아오며, 끝점을 빼면 자기 자신과 만나지 않는다.
• 교수는 좌표의 절댓값이 100을 넘는 점을 지나지 않는다. 이 조건이 이어 붙인 행동 문자열의 길이도 함께 제한한다.

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄에 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 주머니 전체의 넓이다. 이 넓이는 항상 정수이므로 소수점 없이 정수로 출력한다.

아래 그림은 예제 테스트 케이스에 담긴 두 산책을 그린 것이다.