题目描述

你想要构造一个特定的目标字符串 $S$，它仅由小写英文字母组成。初始时你有一个空字符串，并且允许执行以下操作：

• 在字符串末尾添加任意一个小写字母。
• 将字符串中的任意子串（即从字符串中某个起始位置到某个结束位置之间的所有字符）复制到剪贴板。执行此操作会覆盖剪贴板中原有的内容。剪贴板初始为空。
• 将剪贴板的全部内容添加到字符串末尾（剪贴板内容不变）。

请问构造目标字符串所需的最少操作次数是多少？注意，你必须精确地构造出目标字符串，不能有多余的字母。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个目标字符串 $S$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是构造目标字符串所需的最少操作次数（如题目描述所述）。

3
abcabab
aaaaaaaaaaa
vnsdmvnsnsdmkvdmkvnsdmk

Case #1: 6
Case #2: 7
Case #3: 15

提示

样例 #1 的最优解法为：

1. 输入 a。
2. 输入 b。
3. 输入 c。
4. 复制 ab 到剪贴板。
5. 在字符串末尾粘贴 ab。
6. 在字符串末尾粘贴 ab。

样例 #2 的最优解法为：

1. 输入 a。
2. 输入 a。
3. 输入 a。
4. 复制 aaa 到剪贴板。
5. 在字符串末尾粘贴 aaa。
6. 复制 aaaaa 到剪贴板。
7. 在字符串末尾粘贴 aaaaa。

限制条件

$S$ 仅由小写英文字母 a 到 z 组成。

小数据集（测试集 1 – 可见）

$1 \le T \le 100$。

$1 \le$ $S$ 的长度 $\le 6$。

大数据集（测试集 2 – 隐藏）

$1 \le T \le 100$。

$1 \le$ $S$ 的长度 $\le 300$。

翻译由 DeepSeek V4 Pro 完成