Cutting Strings

You are given a string $s$ and an integer $k$. You can remove at most $k$ non-intersecting substrings from $s$. Your task is to find the alphabetically (i.e., dictionary order) largest resulting string.

For example, with string **abcdcada**
and $k{=}2$, you can
choose the substrings **[abc]d[ca]da** and
remove them to get **dda**.

Each input will begin with a line with a single integer $c$ ($1\! \le \! c\! \le \! 2{\cdot }10^5$), which is the number of cases you must solve.

Each of the next $c$ lines will contain an integer $k$ and a string $s$ ($1\! \le \! k\! \le \! |s|\! \le \! 10^5, s\! \in \! [a{-}z]^*$), separated by a space.

The total length of all strings in the input will be at most $10^6$.

Output the largest string, alphabetically, that you can get by removing $k$ or fewer non-intersecting substrings from $s$.

Sample Input 1 | Sample Output 1 |
---|---|

4 2 abcdcada 1 ababb 2 ababb 1 dadbdcdbdad |
dda bb bbb ddcdbdad |