Masha is studying large numbers. She has placed $$$n$$$ cards in a row. Each card has a digit from $$$1$$$ to $$$9$$$ written on it. Together, they form an $$$n$$$-digit integer $$$s$$$.
In one operation, Masha can take two adjacent cards and swap them (she cannot rotate the cards, turning one digit into another). Masha can perform no more than $$$k$$$ operations. What is the minimum $$$n$$$-digit number that can be obtained as a result?
The first line contains an integer $$$t$$$: the number of test cases ($$$1 \le t \le 100\,000$$$). The following lines contain the test cases.
Each test case is given on a line containing two integers $$$s$$$ and $$$k$$$ separated by a space. The integer $$$s$$$ is positive and consists of digits from $$$1$$$ to $$$9$$$. Additionally, $$$0 \le k \le 10^{18}$$$.
The total number of digits in all numbers $$$s$$$ does not exceed $$$100\,000$$$.
For each test case, print a line with the answer: the minimum $$$n$$$-digit number that can be obtained from $$$s$$$ by swapping two adjacent digits no more than $$$k$$$ times.
4321 09 121241127 10692 1
321 9 11122247 629