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

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

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

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

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