Start

2019-03-02 18:00 UTC

NAIPC 2019

End

2019-03-02 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -84 days 13:42:34

Time elapsed

5:00:00

Time remaining

0:00:00

Problem I
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.

Input

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

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