Lexicographically Smallest Subsequence

You are given a string \( S \) consisting only of digits and an integer \( K \). Your task is to select exactly \( K \) digits from \( S \) (by possibly removing some digits without changing the order of the remaining digits) such that the resulting subsequence is the lexicographically smallest possible.

Note: A sequence \( A = a_1a_2\ldots a_K \) is lexicographically smaller than \( B = b_1b_2\ldots b_K \) if there exists an index \( i \) (\( 1 \leq i \leq K \)) such that \( a_1 = b_1, a_2 = b_2, \ldots, a_{i-1} = b_{i-1} \) and \( a_i < b_i \).

Example:
If \( S = "654321" \) and \( K = 2 \), one valid way to select digits is to choose the last two digits, forming "21", which is the lexicographically smallest subsequence of length 2.

Use a greedy algorithm with a stack to solve this problem: iterate through the digits of \( S \) and maintain a stack to build your answer. At each step, while conditions allow, pop from the stack if the current digit is smaller than the top of the stack and if there are enough remaining digits to complete the subsequence of length \( K \). Finally, if the stack length is less than \( K \), push the current digit onto the stack.

inputFormat

The input is read from stdin and has the following format:

T
S1 K1
S2 K2
...
ST KT

Here, the first line contains an integer \( T \) denoting the number of test cases. Each of the next \( T \) lines contains a string \( S \) (composed of digits) followed by an integer \( K \) separated by whitespace.

outputFormat

For each test case, output a single line to stdout containing the lexicographically smallest subsequence of length \( K \) obtained from \( S \).

## sample

3
654321 2
123456 3
54321 2

21
123
21

</p>