Description

Blue 和 Orange 是两台友好的机器人。一个邪恶的电脑主谋把它们分别关在不同的走廊里进行测试，之后可能会给它们蛋糕。

每条走廊里都有 $100$ 个按钮，编号为正整数 $\{1, 2, \ldots, 100\}$。按钮 $k$ 总是在距离走廊起点 $k$ 米的位置，两个机器人都从按钮 $1$ 开始。在一秒钟内，机器人可以向任意方向走一米，或者按下当前位置的按钮一次，或者停在当前位置不按按钮。为了完成测试，机器人需要按照给定顺序依次按下某些按钮。两个机器人都提前知道完整的按钮序列。请问它们最少需要多少秒才能完成任务？

例如，考虑如下按钮序列：

O $2$, B $1$, B $2$, O $4$

这里，O $2$ 表示 Orange 走廊上的按钮 $2$，B $1$ 表示 Blue 走廊上的按钮 $1$，以此类推。机器人可以用如下策略在 $6$ 秒内完成按钮序列：

注意，Blue 必须等到 Orange 完全按完 O $2$ 之后，才能开始按 B $1$。

Input Format

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试数据。

每组测试数据为一行，首先是一个正整数 $N$，表示需要按下的按钮数量。接下来有 $N$ 个形如 "$R_i P_i$" 的项，其中 $R_i$ 表示机器人颜色（始终为 'O' 或 'B'），$P_i$ 表示按钮的位置。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试编号（从 1 开始），$y$ 是机器人按顺序按下所有按钮所需的最少秒数。

3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1

Case #1: 6
Case #2: 100
Case #3: 4

Hint

限制条件

• 对所有 $i$，$1 \leq P_i \leq 100$。

小数据集（10 分，测试集 1 - 可见）

• $1 \leq T \leq 20$。
• $1 \leq N \leq 10$。
• 时间限制：3 秒。

大数据集（10 分，测试集 2 - 隐藏）

• $1 \leq T \leq 100$。
• $1 \leq N \leq 100$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译