给你一个字符串 $$$s$$$。您可以对字符重新排序以形成字符串 $$$t$$$。将 $$$t_{\mathrm{max}}$$$ 定义为 $$$t$$$ 和 $$$t$$$ 按相反顺序的字典最大值。
给定 $$$s$$$,确定 $$$s$$$ 的所有重新排序 $$$t$$$ 中 $$$t_{\mathrm{max}}$$$ 按字典顺序排列的最小值。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含字符串 $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$)。 $$$s$$$ 仅由小写英文字母组成。
保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印 $$$t_{\mathrm{max}}$$$ 在 $$$s$$$ 的所有重新排序中按字典顺序排列的最小值 $$$t$$$。
示例
输入 #1
12 a aab abb abc aabb aabbb aaabb abbb abbbb abbcc eaga ffcaba
输出 #1
a aba bab bca abba abbba ababa bbab bbabb bbcca agea acffba
注意
对于第一个测试用例,$$$s$$$ 只有一次重新排序,即“a”。
对于第二个测试用例,$$$s$$$ 进行了 3 次重新排序。
- $$$t = \mathtt{aab}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$$$
- $$$t = \mathtt{aba}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$$$
- $$$t = \mathtt{baa}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$$$
所有情况下 $$$t_{\mathrm{max}}$$$ 的字典最小值是“aba”。