P16103 [ICPC 2019 NAIPC] 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 \leq c \leq 2\cdot10^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 \leq k \leq |s| \leq 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$.