A15779 | Insert Digit

You have a positive number of length $n$ and one additional digit.

You can insert this digit anywhere in the number, including at the beginning or at the end.

Your task is to make the result as large as possible.

For example, you have the number $76543$ , and the additional digit is $4$ . Then the maximum number you can get is $765443$ , and it can be obtained in two ways — by inserting a digit after the $3$ th or after the $4$ th digit of the number.

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

The descriptions of the test cases follow.

The first line of the description of each test case contains two integers $n$ and $d$ ( $1 \le n \le 2 \cdot 10^5$ ; $0 \le d \le 9$ ) — the length of the number and an additional digit, respectively.

The second line of the description of each test case contains a string consisting of $n$ digits — the number that you have initially. It is guaranteed that the number does not contain leading zeros.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$ .

For each test case, output a string consisting of $n + 1$ digits — the maximum possible number that can be obtained.