{"raw_statement":[{"iden":"problem statement","content":"A string is called a **beautiful string** if and only if it satisfies the following conditions:\n\n*   Every character is `A`, `B`, or `C`.\n*   No two adjacent characters are the same.\n\nFor example, `AB` and `BCAC` are beautiful strings, while `BB` and `CBAAC` are not.\n\n* * *\n\nYou are given a beautiful string $S$. On this string, you can repeatedly perform the following operation.\n\n*   Operation: Swap two adjacent characters in $S$. Here, $S$ must still be a beautiful string after the swap.\n\nFind the lexicographically smallest string that $S$ can become.\n$T$ test cases are given; solve each of them."},{"iden":"constraints","content":"*   $1\\leq T\\leq 10^5$\n*   $S$ is a beautiful string.\n*   $1\\leq |S|\\leq 10^6$\n*   The sum of $|S|$ over all test cases in a single input is at most $10^6$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$S$"},{"iden":"sample input 1","content":"8\nCAB\nACBCB\nB\nAC\nBACBA\nBABABA\nABCBCAC\nCBABACABCBABABC"},{"iden":"sample output 1","content":"ABC\nABCBC\nB\nAC\nABABC\nBABABA\nABCACBC\nABABACBCACBCBAB\n\nFor each of the first and second test cases, here is a possible way to lexicographically minimize $S$:\n\n*   `CAB` → `ACB` → `ABC`\n*   `ACBCB` → `CABCB` → `CBACB` → `BCACB` → `BCABC` → `BACBC` → `ABCBC`"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}