题目描述

Dave 对手中的基因序列不太满意！

Dave 所在的宇宙中，基因序列是一个小写字母组成的字符串，他正在研究一串基因序列 $S$，为了凑出他心中最美的基因序列，他先准备了一个空基因序列 $T$，然后每次从当前的 $S$ 中选出字典序最大的连续子串，将其取出接到 $T$ 的末尾，直到 $S$ 为空。最终得到的 $T$ 就是 Dave 的得意之作！

虽然还没有开始动手，但是 Dave 迫不及待地想看看最终的结果，这个重任就交给你了。

输入格式

第一行一个整数 $C$ 表示数据组数。

对于每组数据，第一行一个整数 $n$，第二行一个长度为 $n$ 的小写字符串 $S$。

输出格式

共 $C$ 行，第 $i$ 行一个字符串表示第 $i$ 组数据最终的串 $T$。

2
5
abacb
7
abacaba

cbbaa
cababaa

样例解释 1

样例解释：对于第二组数据：

• abacaba 的最大字典序子串是 [4,7] 的 caba，S 变为 aba，T 变为 caba。
• aba 的最大字典序子串是 [2,3] 的 ba，S 变为 a，T 变为 cababa。
• a 的最大字典序子串是 [1,1] 的 a，S 变为空，T 变为 cababaa。

数据范围

对于 $20\%$ 的数据，$\sum n\leq 50$。

对于 $40\%$ 的数据，$\sum n\leq 3000$。

对于另外 $20\%$ 的数据，$S$ 中仅含字母 $\text{a,b}$。

对于 $100\%$ 的数据，$1\leq C\leq 10^5$，$1\leq n\leq 5\times 10^5$，$\sum n\leq 5\times 10^5$，$S$ 中仅包含小写字母。