给定一个长度为 $N$ 且仅包含小写英文字母的字符串 $S$。

你需要将 $S$ 划分成两个不相交的子序列 $X$ 和 $Y$，使得 $S$ 中的每个字符恰好属于其中一个子序列。

不失一般性，假设 $|X| \ge |Y|$（否则交换 $X$ 和 $Y$）。在 $Y$ 的末尾不断添加字符 a，直到 $|Y| = |X|$。

现在定义一个长度为 $|X|$ 的字符串 $Z$，使得对于每个 $1 \le i \le |X|$，都有 $Z_i = \max(X_i, Y_i)$。

求字典序最小的可能字符串 $Z$。

一个序列是另一个序列的子序列，如果它可以通过从任意位置删除若干个（可能是零个或全部）元素而获得。

一个字符串 $U$ 被认为比字符串 $V$ 字典序小，当且仅当满足以下条件之一：

• $U$ 是 $V$ 的前缀，且 $U \neq V$；
• 在 $U$ 和 $V$ 首次出现不同字符的位置，字符串 $U$ 的字符在字母表中的顺序早于字符串 $V$ 中的对应字符。

输入格式

输入按以下格式给出：

T
N
S
...

输出格式

对于每个测试用例，输出一行，包含字典序最小的可能字符串 $Z$。

数据范围

• $1 \le T \le 10^4$
• $1 \le N \le 5000$
• $S$ 是一个长度为 $N$ 且仅包含小写英文字母的字符串。
• 保证所有测试用例的 $N^2$ 之和不超过 $5000^2$。

样例

输入样例 1

3
1
a
2
za
5
ababa

输出样例 1

a
z
aba

说明

测试用例 3：选择 $X = \text{aba}$ 且 $Y = \text{ab}$。在 $Y$ 的末尾添加一个 a 后，我们得到 $Y = \text{aba}$，因此 $Z = \max(\text{aba}, \text{aba}) = \text{aba}$。所以，答案是 $\text{aba}$。