给定一个字符串 $s$ 和一个整数 $k$。你可以从 $s$ 中删除至多 $k$ 个互不相交的子串。你的任务是找到字典序最大的结果字符串。

例如，对于字符串 $\texttt{abcdcada}$ 和 $k=2$，你可以选择删除子串 $\texttt{[abc]d[ca]da}$ 中的 $\texttt{abc}$ 和 $\texttt{ca}$，从而得到 $\texttt{dda}$。

输入格式

输入的第一行包含一个整数 $c$ ($1 \leq c \leq 2 \times 10^5$)，表示你需要解决的测试用例数量。

接下来的 $c$ 行，每行包含一个整数 $k$ 和一个字符串 $s$ ($1 \leq k \leq |s| \leq 10^5, s \in [a-z]^*$)，两者之间用空格分隔。

所有字符串的总长度不超过 $10^6$。

输出格式

输出通过删除至多 $k$ 个互不相交的子串后，能够得到的字典序最大的字符串。

样例

样例输入 1

4
2 abcdcada
1 ababb
2 ababb
1 dadbdcdbdad

样例输出 1

dda
bb
bbb
ddcdbdad