给你一个字符串 $$$s$$$,由小写拉丁字母组成。当字符串 $$$s$$$ 中至少有一个字符重复至少两次时,请执行以下操作:
- 选择索引 $$$i$$$ ($$$1 \le i \le |s|$$$),使得位置 $$$i$$$ 处的字符在字符串 $$$s$$$ 中至少出现两次,并删除位置 $$$i$$$ 处的字符,即将 $$$s$$$ 替换为 $$$s_1 s_2 \ldots s_{i-1} s_{i+1} s_{i+2} \ldots s_n$$$。
例如,如果 $$$s=$$$"codeforces",则您可以应用以下操作序列:
- $$$i=6 \Rightarrow s=$$$"codefrces";
- $$$i=1 \Rightarrow s=$$$"odefrces";
- $$$i=7 \Rightarrow s=$$$"odefrcs";
给定一个给定的字符串 $$$s$$$,找到在应用一定的操作序列后,该字符串中的所有字符都变得唯一后可以获得的按字典顺序排列的最大字符串。
长度为 $$$n$$$ 的字符串 $$$a$$$ 按字典顺序小于长度为 $$$m$$$ 的字符串 $$$b$$$,如果:
- 有一个索引 $$$i$$$ ($$$1 \le i \le \min(n, m)$$$) 使得字符串 $$$a$$$ 和 $$$b$$$ 的第一个 $$$i-1$$$ 字符相同,并且字符串 $$$a$$$ 的第 $$$i$$$ 字符小于字符串的第 $$$i$$$ 个字符$$$b$$$;
- 或字符串 $$$a$$$ 和 $$$b$$$ 中的第一个 $$$\min(n, m)$$$ 字符相同,且 $$$n < m$$$。
例如,字符串 $$$a=$$$"aezakmi" 按字典顺序小于字符串 $$$b=$$$"aezus"。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的特征是字符串 $$$s$$$,由小写拉丁字母组成 ($$$1 \le |s| \le 2 \cdot 10^5$$$)。
保证所有测试用例中字符串的长度总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出在应用一定的操作序列后可以获得的按字典顺序排列的最大字符串,之后字符串中的所有字符都变得唯一。
示例
输入 #1
6 codeforces aezakmi abacaba convexhull swflldjgpaxs myneeocktxpqjpz
输出 #1
odfrces ezakmi cba convexhul wfldjgpaxs myneocktxqjpz