P13189 [GCJ 2016 #1A] The Last Word

在综艺节目 **The Last Word** 中，主持人会在一轮游戏开始时向选手展示一个由大写英文字母组成的字符串 $\mathbf{S}$。选手面前有一块最初为空的白板。接着，主持人会依次按照 $\mathbf{S}$ 中的顺序，将每个字母逐一呈现给选手。当主持人给出第一个字母时，选手需要把它写在白板上；这时白板上的内容就构成了游戏中的第一个单词（虽然它只有一个字母）。之后，每当主持人给出一个新字母，选手必须选择将其写在当前白板单词的开头或末尾，然后主持人再给出下一个字母（或游戏结束，如果没有更多字母）。 例如，对于 $\mathbf{S} = \text{CAB}$，选手在白板上写下 C 之后，可以有如下四种决策路径： - 将 A 写在 C 前面，得到 AC，再将 B 写在 AC 前面，得到 $\text{BAC}$ - 将 A 写在 C 前面，得到 AC，再将 B 写在 AC 后面，得到 $\text{ACB}$ - 将 A 写在 C 后面，得到 CA，再将 B 写在 CA 前面，得到 $\text{BCA}$ - 将 A 写在 C 后面，得到 CA，再将 B 写在 CA 后面，得到 $\text{CAB}$ 当选手按规则写完 $\mathbf{S}$ 的所有字母后，白板上的单词就称为 **last word**。如果选手最终得到的单词，在所有可能得到的 last word 的按字典序排序后的列表中排在最后，则选手获胜。对于上面的例子，获胜的 last word 是 $\text{CAB}$（恰好与原始字符串相同）。对于 $\mathbf{S} = \text{JAM}$，获胜的 last word 是 $\text{MJA}$。 你是下一个参赛选手，主持人刚刚向你展示了字符串 $\mathbf{S}$。请问，你应当如何操作，才能获得获胜的 last word？

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组一行，一个字符串 $\mathbf{S}$。

对于每组测试用例，输出一行 `Case #x: y`，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 为你应当获得的获胜 last word。

**限制条件** - $1 \leqslant \mathbf{T} \leqslant 100$。 **小数据集（9 分，测试集 1 - 可见）** - $1 \leqslant \mathbf{S}$ 的长度 $\leqslant 15$。 **大数据集（11 分，测试集 2 - 隐藏）** - $1 \leqslant \mathbf{S}$ 的长度 $\leqslant 1000$。 翻译由 GPT4.1 完成。