Polygonovich 教授是 Flatland 的一名诚实公民，他喜欢在平面上的整点之间进行随机漫步。他早晨从原点出发，面朝北方。他会执行三种动作：

• 'F'：向前移动一个单位长度。
• 'L'：向左转 90 度。
• 'R'：向右转 90 度。

一天结束时（是的，这是一次漫长的步行！），他回到了原点。除了原点外，他从不访问同一个点两次，因此他的路径围成了一个多边形。在下图中，多边形的内部被涂成了蓝色（暂时忽略点 x、y、z 和 w；稍后会解释它们）：

请注意，只要 Polygonovich 教授转弯次数超过 4 次，该多边形就不是凸多边形。因此，它内部存在凹陷（pockets）。

警告！ 为了增加任务难度，我们对 凹陷 的定义可能与你之前听到的有所不同。

下图中的灰色区域表示该多边形的凹陷。

形式化地，如果一个点 p 不在多边形内部，且满足以下两个条件中的至少一个，则称其位于凹陷中：

• 在 p 的正东和正西方向上都有边界点；或者
• 在 p 的正北和正南方向上都有边界点。

边界点是指 Polygonovich 先生在步行过程中经过的点（包括所有点，而不仅仅是坐标为整数的点）。

再次考虑上面的第一张图。点 x 满足第一个条件；y 同时满足两个条件；z 满足第二个条件。这三个点都在凹陷中。点 w 不在凹陷中。

给定 Polygonovich 的步行路径，你的任务是求出所有凹陷的总面积。

输入格式

输入的第一行包含测试用例的数量 N。接下来是 N 个测试用例。

每个测试用例包含 Polygonovich 教授的一次步行描述。它以一个整数 L 开头。随后是 L 个 "S T" 对，其中 S 是由 'L'、'R' 和 'F' 字符组成的字符串，T 是一个整数，表示 S 重复的次数。换句话说，一个测试用例的输入如下所示：

S1 T1 S2 T2 ... SL TL

所采取的动作是 $T_1$ 个 $S_1$ 的副本，接着是 $T_2$ 个 $S_2$ 的副本，依此类推。

单个测试用例的 "S T" 对可能不会全部在同一行，但字符串 S 不会被拆分到多行。下面的第二个样例展示了这一点。

输出格式

对于每个测试用例，输出一行 "Case #X: Y"，其中 X 是从 1 开始的用例编号，Y 是所有凹陷的总面积。

数据范围

时间限制：8 秒。

内存限制：1GB。

$1 \le N \le 100$

$1 \le T$（上限由下述“小数据集”和“大数据集”部分约束）

路径在连接输入字符串后，不会出现两个连续的转向（即连接后的路径中不会出现 'LL'、'RR'、'LR' 或 'RL'）。路径中至少会有一个 'F'。

所描述的路径不会自交（除了终点），并且最终会回到原点。

小数据集（测试集 1 - 可见；5 分）

$1 \le L \le 100$

每个字符串 S 的长度在 1 到 16 之间（含）。

教授不会访问任何绝对值大于 100 的坐标点。

大数据集（测试集 2 - 隐藏；15 分）

$1 \le L \le 1000$

每个字符串 S 的长度在 1 到 32 之间（含）。

教授不会访问任何绝对值大于 3000 的坐标点。

样例

样例输入 1

2
1
FFFR 4
9
F 6 R 1 F 4 RFF 2 LFF 1
LFFFR 1 F 2 R 1 F 5

样例输出 1

Case #1: 0
Case #2: 4

下图展示了这两个样例测试用例。