Roland 是一位高中数学老师。每天，他都会收到学生们交上来的数百份试卷。对于每一份试卷，他都会仔细地给出一个字母等级：'A'、'B' 或 'C'。（Roland 的学生们太聪明了，不会得到 'D' 或 'F' 这样低的等级。）一旦所有等级都确定了，Roland 就会把试卷交给他的助手——也就是你。你的工作是在每份试卷上盖上正确的等级印章。

你有一个低科技含量但功能齐全的字母印章。要打印一个字母，你需要将对应于该字母的特殊印版安装在印章前端，蘸上墨水，然后盖在试卷上。

有趣的是，当你想要更换字母时，不必取下旧印版，只需在旧印版上直接覆盖一个新的印版即可。事实上，你可以将印章上的印版看作一个栈，支持以下操作：

• 将一个字母压入栈顶。（这相当于在印章前端安装一个新的印版。）
• 从栈顶弹出一个字母。（这相当于从印章前端移除一个印版。）
• 打印栈顶的字母。（这相当于实际使用印章。）当然，要执行此操作，栈中必须有字母。

给定一个字母等级序列（'A'、'B' 和 'C'），你需要多少次操作才能按顺序打印出整个序列？栈最初是空的，并且在完成任务后必须清空。不过，在此过程中，你可以无限量地使用每种印版。

例如，如果你想打印序列 "ABCCBA"，你可以通过 12 次操作完成，如下所示：

输入格式

输入文件的第一行包含测试用例的数量 T。接下来是 T 个测试用例，每行一个。每一行包含一个字符串 S，表示你想要按顺序打印出的字符序列。

输出格式

对于每个测试用例，输出一行 "Case #x: N"，其中 x 是测试用例编号（从 1 开始），N 是打印出 S 所需的最少栈操作次数。

S 是一个非空字符串，仅包含字母 'A'、'B' 和 'C'。

样例

输入格式 1

2
ABCCBA
AAABAAB

输出格式 1

Case #1: 12
Case #2: 13