题目描述

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

例如，对于字符串 abcdcada 和 $k=2$，你可以选择子串 [abc]d[ca]da 并删除它们，得到 dda。

输入格式

每个输入的第一行包含一个整数 $c$（$1 \leq c \leq 2\cdot10^5$），表示你需要解决的测试用例个数。

接下来的 $c$ 行，每行包含一个整数 $k$ 和一个字符串 $s$（$1 \leq k \leq |s| \leq 10^5$，$s$ 由小写字母组成），两者之间用空格分隔。

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

输出格式

对于每个测试用例，输出通过从 $s$ 中删除至多 $k$ 个互不相交的子串所能得到的字典序最大的字符串。

4
2 abcdcada
1 ababb
2 ababb
1 dadbdcdbdad

dda
bb
bbb
ddcdbdad

提示

翻译由 DeepSeek V3.2 完成