{"raw_statement":[{"iden":"problem statement","content":"Given is a string $S$ consisting of `a` and `b`. Find the lexicographically **greatest** string that can be obtained by applying the following operation to $S$ zero or more times:\n\n*   Choose two characters of $S$ that are the same letter. Reverse the string between them and delete the chosen two characters. In other words: let $s_i$ denote the $i$\\-th character of $S$. Choose $i < j$ such that $s_i = s_j$ and replace $S$ with $s_1\\dots s_{i-1}s_{j-1}\\dots s_{i+1}s_{j+1}\\dots s_{|S|}$.\n\nIn this problem, you are given $T$ test cases. The $i$\\-th test case is represented as $S_i$ and asks you to solve the problem above for $S = S_i$."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2\\times 10^5$\n*   $1 \\leq |S_i|\\quad (i=1,\\dots, T)$\n*   $1 \\leq |S_1| + \\dots + |S_T| \\leq 2\\times 10^5$\n*   $S_i$ consists of `a` and `b`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$S_1$\n$\\vdots$\n$S_T$"},{"iden":"sample input 1","content":"20\nabbaa\nbabbb\naabbabaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\nbbabaaaaabbaababaaabbabbbbbaaaaa\nbabbbaaaabaababbbabaabaaaaababaa\nbbaababababbbaaabaabababaabbabab\nabaabbabaabaaaaabaaaabbaabaaaaab\naabababbabbabbabbaaaabbabbbabaab\naabababbabbbbaaaabbaaaaabbaaaabb\nabbbbaabaaabababaaaababababbaabb\naaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb\naaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb\nabababaaababaaabbbbbaaaaaaabbbbb\naabbaaaaababaabbbbbbbbbaabaaabbb\nbabababbababbbababbbbbababbbabbb\nbbbbababbababbbabababbabbabbbbbb\naaaaaaaaaaaaaaaaababababbbabbbbb\naabababbabbabababababababbbbabbb"},{"iden":"sample output 1","content":"bba\nbba\nbbba\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\nbbbbbbbbbbbbbbaaaaaaaa\nbbbbbbbbbbbbbaaaaaaa\nbbbbbbbbbbbbbbbb\nbbbbbbbbbb\nbbbbbbbbbbbbbbbbab\nbbbbbbbbbbbbbb\nbbbbbbbbbbbbbabb\nabbbbbbbbb\nbbbbbbbbbbbbbbbbbbbbbb\nbbbbbbbbbbbbbaaaaaaaaa\nbbbbbbbbbbbbbbbaaaaa\nbbbbbbbbbbbbbbbbbbbbbb\nbbbbbbbbbbbbbbbbbbbbba\nbbbbbbbbbaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbbba\n\n*   In the $1$\\-st test case, we can do the operation for the $1$\\-st and $4$\\-th characters to make $S$ `bba`.\n*   In the $2$\\-nd test case, we can do the operation for the $1$\\-st and $5$\\-th characters to make $S$ `bba`.\n*   In the $3$\\-rd test case, we can do the operation for the $1$\\-st and $2$\\-nd characters to make $S$ `bbabaa`, then do it for the $3$\\-rd and $5$\\-th characters to make $S$ `bbba`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}