{"problem":{"name":"Beautiful String","description":{"content":"A string is called a **beautiful string** if and only if it satisfies the following conditions: *   Every character is `A`, `B`, or `C`. *   No two adjacent characters are the same. For example, `AB","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc066_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc066_f","tags":[],"sample_group":[["8\nCAB\nACBCB\nB\nAC\nBACBA\nBABABA\nABCBCAC\nCBABACABCBABABC","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`"]],"created_at":"2026-03-03 11:01:14"}}