How Big Are the Pockets? (Large)

Professor Polygonovich, an honest citizen of Flatland, likes to walk along the integer points of the plane. He starts at the origin in the morning, facing north, and he only ever does one of three things.

• 'F': move forward one unit of length.
• 'L': turn 90 degrees left.
• 'R': turn 90 degrees right.

At the end of the day (yes, it is a long walk) he is back at the origin. Apart from the origin he never visits the same point twice, so his path encloses a polygon. In the picture below the interior of the polygon is blue. The points $x$, $y$, $z$ and $w$ are explained further down.

Once the professor makes more than four turns the polygon is not convex, so it has pockets.

Warning! The definition of a pocket used here may differ from the one you already know.

The gray area in the next picture is the set of pockets of the polygon.

Formally, a point $p$ is in a pocket if it is not inside the polygon and at least one of the following two conditions holds.

• There is a boundary point directly east of $p$ and a boundary point directly west of $p$.
• There is a boundary point directly north of $p$ and a boundary point directly south of $p$.

A boundary point is any point the professor walks over, not only the ones with integer coordinates.

Look at the first picture again. Point $x$ satisfies the first condition, point $z$ satisfies the second one, and point $y$ satisfies both. All three are in pockets. Point $w$ is not in a pocket.

Given the professor's walk, compute the total area of the pockets.

The first line contains the number of test cases $N$. The $N$ test cases follow.

Each test case describes one walk. It starts with an integer $L$, followed by $L$ pairs "$S$ $T$", where $S$ is a string of the characters 'L', 'R' and 'F', and $T$ is how many times $S$ is repeated.

The input for one test case looks like this.

S1 T1 S2 T2 ... SL TL

The actions taken are $T_1$ copies of $S_1$, then $T_2$ copies of $S_2$, and so on.

The pairs of one test case are not always on the same line, but a string $S$ is never split across lines. The second test case of the first example shows this.

Limits

• $1 \le N \le 100$
• $1 \le T$. The coordinate limit below bounds how large $T$ can be.
• The concatenated path never changes direction twice in a row, so it contains no 'LL', 'RR', 'LR' or 'RL'. It contains at least one 'F'.
• The path does not cross itself except at its end, and it ends back at the origin.
• $1 \le L \le 1000$
• The length of each string $S$ is between 1 and 32, inclusive.
• The professor never visits a point with a coordinate larger than 3000 in absolute value.

For each test case print one line in the form Case #X: Y, where $X$ is the 1-based test case number and $Y$ is the total area of all pockets. That area is always an integer, so print it as an integer.

The picture below shows the two walks of the first example.