How Big Are the Pockets? (Small)

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 makes only three kinds of moves.

• 'F': move one unit forward.
• 'L': turn 90 degrees to the left.
• 'R': turn 90 degrees to the 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 4 turns the polygon is not convex, so it has pockets.

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

The gray area below is the set of pockets of the polygon.

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

• There are boundary points directly east of $p$ and directly west of $p$.
• There are boundary points directly north of $p$ and directly south of $p$.

The boundary points are the points the professor walks over. They include every point of the traversed segments, not only the points 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 points 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 of the form "$S$ $T$", where $S$ is a string of the characters 'L', 'R' and 'F', and $T$ is an integer telling how many times $S$ is repeated.

So the input of one test case looks like this.

S1 T1 S2 T2 ... SL TL

The moves the professor makes 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 necessarily all on the same line, but a single string $S$ is never split across lines.

Limits

• $1 \le N \le 100$
• $1 \le L \le 100$
• the length of each string $S$ is between 1 and 16, inclusive
• $1 \le T$
• the concatenated path never changes direction twice in a row, so none of 'LL', 'RR', 'LR' and 'RL' occurs in it, and it contains at least one 'F'
• the path ends at the origin and does not touch itself anywhere else
• the professor never visits a point with a coordinate larger than 100 in absolute value, and that condition also bounds the length of the concatenated move string

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

The picture below draws the two walks of the example test case.