问题陈述

给定一个由 a 和 b 组成的字符串 $S$。找到可以通过对 $S$ 零次或多次应用以下操作得到的字典序最大的字符串：

• 选择 $S$ 中相同字母的两个字符。翻转它们之间的字符串，并删除选择的两个字符。换句话说，令 $s_i$ 表示 $S$ 的第 $i$ 个字符。选择 $i < j$，使得 $s_i = s_j$，并用 $s_1\\dots s_{i-1}s_{j-1}\\dots s_{i+1}s_{j+1}\\dots s_{|S|}$ 替换 $S$。

在这个问题中，给出了 $T$ 个测试用例。第 $i$ 个测试用例表示为 $S_i$，要求你解决上述问题，其中 $S = S_i$。

约束条件

• $1 \\leq T \\leq 2\\times 10^5$
• $1 \\leq |S_i|\\quad (i=1,\\dots, T)$
• $1 \\leq |S_1| + \\dots + |S_T| \\leq 2\\times 10^5$
• $S_i$ 由 a 和 b 组成。

输入

输入以以下格式从标准输入给出：

$T$ $S_1$ $\\vdots$ $S_T$

输出

输出 $T$ 行。第 $i$ 行应包含可以通过对 $S_i$ 零次或多次应用操作得到的字典序最大的字符串。

示例输入1

20
abbaa
babbb
aabbabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbabaaaaabbaababaaabbabbbbbaaaaa
babbbaaaabaababbbabaabaaaaababaa
bbaababababbbaaabaabababaabbabab
abaabbabaabaaaaabaaaabbaabaaaaab
aabababbabbabbabbaaaabbabbbabaab
aabababbabbbbaaaabbaaaaabbaaaabb
abbbbaabaaabababaaaababababbaabb
aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb
aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb
abababaaababaaabbbbbaaaaaaabbbbb
aabbaaaaababaabbbbbbbbbaabaaabbb
babababbababbbababbbbbababbbabbb
bbbbababbababbbabababbabbabbbbbb
aaaaaaaaaaaaaaaaababababbbabbbbb
aabababbabbabababababababbbbabbb

示例输出1

bba
bba
bbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbaaaaaaaa
bbbbbbbbbbbbbaaaaaaa
bbbbbbbbbbbbbbbb
bbbbbbbbbb
bbbbbbbbbbbbbbbbab
bbbbbbbbbbbbbb
bbbbbbbbbbbbbabb
abbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbaaaaaaaaa
bbbbbbbbbbbbbbbaaaaa
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbba

• 在第 1 个测试用例中，我们可以对第 1 和第 4 个字符进行操作，使得 $S$ 变为 bba。
• 在第 2 个测试用例中，我们可以对第 1 和第 5 个字符进行操作，使得 $S$ 变为 bba。
• 在第 3 个测试用例中，我们可以对第 1 和第 2 个字符进行操作，使得 $S$ 变为 bbabaa，然后对第 3 和第 5 个字符进行操作，使得 $S$ 变为 bbba。