Roland 是一位高中数学老师。每天，他都会收到学生们交上来的数百份试卷。对于每一份试卷，他都会仔细地给出一个字母等级：'A'、'B' 或 'C'。（Roland 的学生们太聪明了，不会得到 'D' 或 'F' 这样低的等级。）一旦所有等级都确定了，Roland 就会把试卷交给他的助手——也就是你。你的工作是在每份试卷上盖上正确的等级印章。
你有一个低科技含量但功能齐全的字母印章。要打印一个字母，你需要将对应于该字母的特殊印版安装在印章前端，蘸上墨水，然后盖在试卷上。
有趣的是，当你想要更换字母时，不必取下旧印版，只需在旧印版上直接覆盖一个新的印版即可。事实上，你可以将印章上的印版看作一个栈，支持以下操作：
- 将一个字母压入栈顶。（这相当于在印章前端安装一个新的印版。）
- 从栈顶弹出一个字母。（这相当于从印章前端移除一个印版。）
- 打印栈顶的字母。（这相当于实际使用印章。）当然，要执行此操作，栈中必须有字母。
给定一个字母等级序列（'A'、'B' 和 'C'），你需要多少次操作才能按顺序打印出整个序列？栈最初是空的，并且在完成任务后必须清空。不过，在此过程中，你可以无限量地使用每种印版。
例如，如果你想打印序列 "ABCCBA"，你可以通过 12 次操作完成，如下所示：
| 操作 | 已打印内容 | 栈 |
|---|---|---|
| 0. - | - | - |
| 1. Push A | - | A |
| 2. Print | A | A |
| 3. Push B | A | AB |
| 4. Print | AB | AB |
| 5. Push C | AB | ABC |
| 6. Print | ABC | ABC |
| 7. Print | ABCC | ABC |
| 8. Pop | ABCC | AB |
| 9. Print | ABCCB | AB |
| 10. Pop | ABCCB | A |
| 11. Print | ABCCBA | A |
| 12. Pop | ABCCBA | - |
输入格式
输入文件的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例，每行一个。每一行包含一个字符串 $S$，表示你想要按顺序打印出的字符序列。
输出格式
对于每个测试用例，输出一行 "Case #x: N"，其中 x 是测试用例编号（从 1 开始），N 是打印出 $S$ 所需的最少栈操作次数。
数据范围
时间限制：每个测试点 5 秒。
空间限制：1GB。
$S$ 是一个非空字符串，仅包含字母 'A'、'B' 和 'C'。
小数据规模（测试集 1 - 可见；8 分）
$1 \le T \le 100$。
$S$ 的长度最多为 100。
大数据规模（测试集 2 - 隐藏；19 分）
$1 \le T \le 20$。
$S$ 的长度最多为 7000。
样例
输入格式 1
2 ABCCBA AAABAAB
输出格式 1
Case #1: 12 Case #2: 13