포켓은 얼마나 큰가?

Flatland의 정직한 시민인 Professor Polygonovich는 평면의 정수 좌표점들을 따라 무작위로 걷는 것을 좋아한다. 그는 아침에 원점에서 북쪽을 바라보며 출발한다. 그가 하는 행동에는 세 가지 종류가 있다:

• 'F': 길이 한 단위만큼 앞으로 이동한다.

• 'L': 왼쪽으로 90도 회전한다.

• 'R': 오른쪽으로 90도 회전한다.

하루가 끝날 때(그렇다, 긴 산책이다!) 그는 원점으로 돌아온다. 원점을 제외하고는 같은 점을 두 번 방문하지 않으므로, 그의 경로는 하나의 다각형을 둘러싼다. 다음 그림에서 다각형의 내부는 파란색으로 칠해져 있다(지금은 점 x, y, z, w를 무시하라. 곧 설명할 것이다):

Professor Polygonovich가 4번보다 많이 회전하기만 하면 다각형은 볼록하지 않다는 점에 유의하라. 따라서 그 안에는 포켓이 있다.

경고! 과제를 더 어렵게 하기 위해, 여기서 사용하는 포켓의 정의는 여러분이 이전에 들어 본 정의와 다를 수도 있다.

아래의 회색 영역은 다각형의 포켓을 나타낸다.

엄밀히 말해, 점 p가 다각형의 내부에 있지 않고 다음 두 조건 중 적어도 하나가 성립하면 p가 포켓 안에 있다고 한다.

• p의 정확히 동쪽과 서쪽 양쪽에 경계점이 있다. 또는

• p의 정확히 북쪽과 남쪽 양쪽에 경계점이 있다.

경계점은 Mr. Poligonovich가 산책하면서 지나간 점들이다(정수 좌표를 갖는 점뿐만 아니라 모든 점을 포함한다).

위의 첫 번째 그림을 다시 살펴보자. 점 x는 첫 번째 조건을 만족하고, y는 두 조건을 모두 만족하며, z는 두 번째 조건을 만족한다. 이 세 점은 모두 포켓 안에 있다. 점 w는 포켓 안에 있지 않다.

Polygonovich의 산책 경로가 주어질 때, 모든 포켓의 총넓이를 구하는 것이 여러분의 과제이다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ N ≤ 100 1 ≤ T (문제 설명의 "Small dataset" 및 "Large dataset" 절에 있는 제약 조건에 의해 상한이 정해진다) 입력 문자열들을 이어 붙인 경로에는 방향 전환이 연속으로 두 번 나타나지 않는다(즉, 이어 붙인 경로에는 'LL', 'RR', 'LR', 'RL' 중 어느 것도 나타나지 않는다). 경로에는 적어도 하나의 'F'가 있다. 설명된 경로는 마지막을 제외하면 자기 자신과 교차하지 않으며, 원점으로 돌아와 끝난다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ L ≤ 100 각 문자열 S의 길이는 1 이상 16 이하이다. 교수는 어느 좌표의 절댓값도 100보다 큰 점을 방문하지 않는다.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ L ≤ 1000 각 문자열 S의 길이는 1 이상 32 이하이다. 교수는 어느 좌표의 절댓값도 3000보다 큰 점을 방문하지 않는다.

입력의 첫 번째 줄에는 테스트 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

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

다시 말해, 하나의 테스트 케이스에 대한 입력은 다음과 같은 형태이다:

S_{1} T_{1} S_{2} T_{2} ... S_{L} T_{L}

수행하는 행동들은 $S_{1}$의 복사본 $T_{1}$개를 이어 붙이고, 그 뒤에 $S_{2}$의 복사본 $T_{2}$개를 이어 붙이는 식으로 구성된다.

하나의 테스트 케이스에 대한 "S T" 쌍이 모두 같은 줄에 있지 않을 수도 있지만, 문자열 S가 여러 줄에 걸쳐 나뉘지는 않는다. 아래의 두 번째 예제가 이를 보여 준다.

각 테스트 케이스마다 "Case #X: Y"을 포함하는 한 줄을 출력한다. 여기서 X는 1부터 세는 테스트 케이스 번호이고, Y는 모든 포켓의 총넓이이다.

다음 그림은 두 예제 테스트 케이스를 보여 준다.