시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB2710947.368%

문제

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.

예제 입력 1

4
321 0
9 1
21241127 10
692 1

예제 출력 1

321
9
11122247
629