题目描述

我们将满足以下条件的字符串称为美丽字符串：

• 每个字符都是 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

输入

8
CAB
ACBCB
B
AC
BACBA
BABABA
ABCBCAC
CBABACABCBABABC

输出

ABC
ABCBC
B
AC
ABABC
BABABA
ABCACBC
ABABACBCACBCBAB

说明/提示

限制

• $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 翻译