주머니는 얼마나 큰가 (Large)

플랫랜드의 정직한 시민 폴리고노비치 교수는 평면의 격자점을 따라 걷기를 좋아한다. 아침에 원점에서 북쪽을 보고 출발하며, 하는 행동은 다음 세 가지뿐이다.

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

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

주의! 이 문제에서 쓰는 주머니의 정의는 이미 아는 정의와 다를 수 있다.

다음 그림의 회색 영역이 이 다각형의 주머니다.

엄밀히 말하면, 점 $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 T$ 이며, $T$ 의 상한은 아래 좌표 제한이 정한다.
이어 붙인 경로에서 방향 전환이 두 번 연속으로 나오지 않는다. 즉 'LL', 'RR', 'LR', 'RL'은 나타나지 않는다. 경로에는 'F'가 적어도 하나 있다.
경로는 끝을 빼면 자기 자신과 교차하지 않고, 원점에서 끝난다.
$1 \le L \le 1000$
각 문자열 $S$ 의 길이는 1 이상 32 이하다.
교수는 좌표의 절댓값이 3000보다 큰 점을 지나지 않는다.

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

아래 그림은 첫 번째 예제에 있는 산책 두 개를 나타낸다.