Description

给定一个由大写英文字母组成的字符串。你可以选择高亮其中任意数量的字母（可以是全部、部分或不选）。被高亮的字母不需要是连续的。然后，通过从左到右处理字母生成一个新字符串：未高亮的字母在新字符串中只出现一次，而被高亮的字母会重复出现两次。

例如，初始字符串为 HELLOWORLD 时，你可以高亮 H、第一个和最后一个 L 以及最后一个 O，得到：HELLOWORLD $\Rightarrow$ HHELLLOWOORLLD。类似地，如果什么都不高亮，得到的是原字符串 HELLOWORLD；如果全部高亮，则得到 HHEELLLLOOWWOORRLLDD。注意：相同的字母可以独立选择是否高亮。

对于一个给定的字符串，根据高亮选择的不同，可以生成多种不同的结果字符串。在所有可能的生成字符串中，输出按字典序排列最靠前的一个。

注：若字符串 $s$ 是字符串 $t$ 的前缀，或者 $s$ 和 $t$ 在第一个不同字符处 $s$ 的字母在字母表中更靠前，则认为 $s$ 在字典序中排在 $t$ 之前。例如以下字符串按字典序排列为：CODE, HELLO, HI, HIM, HOME, JAM。

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个测试用例单独一行，包含一个字符串 $\mathbf{S}$。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是通过上述过程从 $\mathbf{S}$ 生成的所有可能字符串中字典序最小的那个。

3
PEEL
AAAAAAAAAA
CODEJAMDAY

Case #1: PEEEEL
Case #2: AAAAAAAAAA
Case #3: CCODDEEJAAMDAAY

Hint

样例解释

在样例 #1 中，所有可能的生成字符串按字典序排列为：PEEEEL, PEEEELL, PEEEL, PEEELL, PEEL, PEELL, PPEEEEL, PPEEEELL, PPEEEL, PPEEELL, PPEEL 和 PPEELL。

在样例 #2 中，所有可能的生成字符串都只包含字母 A，其中最短的字符串字典序最靠前，因为它是其他所有字符串的前缀。

在样例 #3 中，从 CODEJAMDAY 可以生成 1024 种不同的字符串，其中 CCODDEEJAAMDAAY 是字典序最小的一个。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• 字符串 $\mathbf{S}$ 中的每个字符都是大写英文字母。

测试集 1（10 分，可见评测结果）

• $1 \leq$ 字符串 $\mathbf{S}$ 的长度 $\leq 10$。

测试集 2（15 分，隐藏评测结果）

• $1 \leq$ 字符串 $\mathbf{S}$ 的长度 $\leq 100$。

翻译由 DeepSeek V3 完成