给定一个由大写英文字母组成的字符串。你可以高亮任意数量的字母（可以全部高亮，也可以一个都不高亮）。被高亮的字母不需要连续。然后，通过从左到右处理这些字母来生成一个新字符串：非高亮字母在新字符串中追加一次，而高亮字母追加两次。

例如，如果初始字符串为 HELLOWORLD，你可以高亮 H、第一个和最后一个 L 以及最后一个 O，从而得到 HHELLLOWOORLLD。同样，如果你不进行任何高亮，你将得到 HELLOWORLD；如果你高亮所有字母，你将得到 HHEELLLLOOWWOORRLLDD。注意，同一个字母的每次出现都可以独立地被高亮。

给定一个字符串，根据高亮选择的不同，可以通过此过程得到多个字符串。在所有这些字符串中，输出按字母顺序（也称为字典序）排列最靠前的那一个。

注意：如果字符串 $s$ 是字符串 $t$ 的前缀，或者在 $s$ 和 $t$ 的第一个不同字符处，$s$ 中的字符在字母表中比 $t$ 中的字符更靠前，则称字符串 $s$ 在字母顺序上排在字符串 $t$ 之前。例如，这些字符串按字母顺序排列为：CODE, HELLO, HI, HIM, HOME, JAM。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例由包含单个字符串 $S$ 的单行描述。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是可以通过上述过程从 $S$ 生成的所有字符串中，按字母顺序排列最靠前的那一个。

数据范围

时间限制：2 秒。 内存限制：1 GB。 $1 \le T \le 100$。 $S$ 的每个字符都是大写英文字母。

子任务

测试集 1（可见判定） $1 \le |S| \le 10$。

测试集 2（隐藏判定） $1 \le |S| \le 100$。

样例

样例输入 1

3
PEEL
AAAAAAAAAA
CODEJAMDAY

样例输出 1

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

说明 1

在样例 1 中，按字母顺序排列，所有可以得到的字符串为： PEEEEL, PEEEELL, PEEEL, PEEELL, PEEL, PEELL, PPEEEEL, PPEEEELL, PPEEEL, PPEEELL, PPEEL 和 PPEELL。

在样例 2 中，每个可以得到的字符串都只包含 A。其中最短的字符串在字母顺序上最靠前，因为它是一切其他字符串的前缀。

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

Figure 1. Example of highlighting letters in HELLOWORLD to get HHELLLOWOORLLD