N. Number Reduction
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a positive integer $$$x$$$.

You can apply the following operation to the number: remove one occurrence of any digit in such a way that the resulting number does not contain any leading zeroes and is still a positive integer. For example, $$$10142$$$ can be converted to $$$1142$$$, $$$1042$$$, $$$1012$$$ or $$$1014$$$ (note that $$$0142$$$ is not a valid outcome); $$$10$$$ can be converted to $$$1$$$ (but not to $$$0$$$ since it is not positive).

Your task is to find the minimum positive integer that you can obtain from $$$x$$$ if you can apply the aforementioned operation exactly $$$k$$$ times.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$x$$$ ($$$1 \le x < 10^{500000}$$$).

The second line contains a single integer $$$k$$$ ($$$0 \le k < |x|$$$), where $$$|x|$$$ is the length of the number $$$x$$$.

The sum of $$$|x|$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum positive number that you can obtain from $$$x$$$ if you can apply the operation exactly $$$k$$$ times.

Example
Input
5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3
Output
1
1337
321
344128
7052