AT_agc066_f [AGC066F] Beautiful String

我们将满足以下条件的字符串称为**美丽字符串**： - 每个字符都是 `A`、`B` 或 `C` 之一。 - 任意相邻的 $2$ 个字符都不相同。 例如，`AB`、`BCAC` 是美丽字符串，而 `BB`、`CBAAC` 不是美丽字符串。 ------ 给定一个美丽字符串 $S$，你可以对其反复进行如下操作： - 操作：交换 $S$ 中相邻的 $2$ 个字符，但交换后得到的 $S$ 也必须是美丽字符串。 请你求出最终可能得到的字典序最小的字符串 $S$。 有 $T$ 个测试用例，请分别输出每个测试用例的答案。

输入通过标准输入给出，格式如下： > $T$ > $\text{case}_1$ > $\vdots$ > $\text{case}_T$ 每个测试用例输入格式如下： > $S$

请输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例最终可能得到的字典序最小的字符串。

### 限制 - $1\leq T\leq 10^5$ - $S$ 是美丽字符串。 - $1\leq |S|\leq 10^6$ - 所有测试用例中 $|S|$ 的总和不超过 $10^6$。 ### 样例解释 1 对于第 $1$、$2$ 个测试用例，以下是将 $S$ 字典序最小化的一种方式： - `CAB` → `ACB` → `ABC` - `ACBCB` → `CABCB` → `CBACB` → `BCACB` → `BCABC` → `BACBC` → `ABCBC` 由 ChatGPT 4.1 翻译