在游戏节目“最后一个单词”（The Last Word）中，主持人首先向参赛者展示一个由大写英文字母组成的字符串 $S$。参赛者拥有一个初始为空的白板。主持人随后会按照 $S$ 中字母出现的顺序，逐个向参赛者展示这些字母。当主持人展示第一个字母时，参赛者将其写在白板上；这算作游戏中的第一个单词（即使它只有一个字母长）。此后，每当主持人展示一个字母时，参赛者必须在主持人进行下一个字母（或者如果已无剩余字母，则结束游戏）之前，将该字母写在白板上现有单词的开头或结尾。

例如，对于 $S = \text{CAB}$，在白板上写下单词 $\text{C}$ 后，参赛者可以进行以下四种选择之一：

• 将 $\text{A}$ 放在 $\text{C}$ 前形成 $\text{AC}$，然后将 $\text{B}$ 放在 $\text{AC}$ 前形成 $\text{BAC}$
• 将 $\text{A}$ 放在 $\text{C}$ 前形成 $\text{AC}$，然后将 $\text{B}$ 放在 $\text{AC}$ 后形成 $\text{ACB}$
• 将 $\text{A}$ 放在 $\text{C}$ 后形成 $\text{CA}$，然后将 $\text{B}$ 放在 $\text{CA}$ 前形成 $\text{BCA}$
• 将 $\text{A}$ 放在 $\text{C}$ 后形成 $\text{CA}$，然后将 $\text{B}$ 放在 $\text{CA}$ 后形成 $\text{CAB}$

当参赛者按照给定规则写完 $S$ 中的所有字母后，得到的单词被称为“最后一个单词”。如果参赛者的最后一个单词在所有可能产生的最后一个单词的按字母顺序排序的列表中排在最后，则参赛者获胜。对于上面的例子，获胜的最后一个单词是 $\text{CAB}$（恰好与原始字符串相同）。对于 $S = \text{JAM}$ 的游戏，获胜的最后一个单词是 $\text{MJA}$。

你是该节目的下一位参赛者，主持人刚刚向你展示了字符串 $S$。你应该写出什么样的获胜的最后一个单词？

输入格式

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

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是题目描述中所述的获胜的最后一个单词。

数据范围

$1 \le T \le 100$。

小型数据集（测试集 1 - 可见）： $1 \le \text{length of } S \le 15$。

大型数据集（测试集 2 - 隐藏）： $1 \le \text{length of } S \le 1000$。

样例

输入格式 1

7
CAB
JAM
CODE
ABAAB
CABCBBABC
ABCABCABC
ZXCASDQWE

输出格式 1

Case #1: CAB
Case #2: MJA
Case #3: OCDE
Case #4: BBAAA
Case #5: CCCABBBAB
Case #6: CCCBAABAB
Case #7: ZXCASDQWE