310294: CF1811A. Insert Digit

A. Insert Digittime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

11
5 4
76543
1 0
1
2 5
44
3 6
666
5 6
13579
5 8
97531
19 4
9876543210123456789
5 7
73737
8 1
20000000
7 0
7058959
12 1
828127127732

Output

765443
10
544
6666
613579
987531
98765443210123456789
773737
210000000
70589590
8281271277321

题目大意：
给定一个正整数和一个额外的数字，你可以将这个额外的数字插入到整数中的任何位置，包括开头和结尾，目标是使得结果尽可能大。例如，对于整数76543和额外数字4，可以得到最大的数765443。需要编写程序，对于给定的多个测试用例，输出插入额外数字后可能得到的最大数。

输入数据格式：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 接下来每两个连续的行描述一个测试用例：
- 第一行包含两个整数n和d（1 ≤ n ≤ 2 × 10^5；0 ≤ d ≤ 9），分别表示整数的长度和额外的数字。
- 第二行包含一个由n个数字组成的字符串，表示你最初拥有的数。保证这个数不包含前导零。
- 保证所有测试用例的n之和不超过2 × 10^5。

输出数据格式：
- 对于每个测试用例，输出一个包含n+1个数字的字符串，表示可以得到的最大数。

示例：
输入：
```
11
5 4
76543
1 0
1
2 5
44
3 6
666
5 6
13579
5 8
97531
19 4
9876543210123456789
5 7
73737
8 1
20000000
7 0
7058959
12 1
828127127732
```
输出：
```
765443
10
544
6666
613579
987531
98765443210123456789
773737
210000000
70589590
8281271277321
```

请注意，示例中的输入和输出数据仅为展示格式，实际解决问题需要根据输入的具体数字来决定额外数字的插入位置。题目大意： 给定一个正整数和一个额外的数字，你可以将这个额外的数字插入到整数中的任何位置，包括开头和结尾，目标是使得结果尽可能大。例如，对于整数76543和额外数字4，可以得到最大的数765443。需要编写程序，对于给定的多个测试用例，输出插入额外数字后可能得到的最大数。 输入数据格式： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 接下来每两个连续的行描述一个测试用例： - 第一行包含两个整数n和d（1 ≤ n ≤ 2 × 10^5；0 ≤ d ≤ 9），分别表示整数的长度和额外的数字。 - 第二行包含一个由n个数字组成的字符串，表示你最初拥有的数。保证这个数不包含前导零。 - 保证所有测试用例的n之和不超过2 × 10^5。 输出数据格式： - 对于每个测试用例，输出一个包含n+1个数字的字符串，表示可以得到的最大数。 示例： 输入： ``` 11 5 4 76543 1 0 1 2 5 44 3 6 666 5 6 13579 5 8 97531 19 4 9876543210123456789 5 7 73737 8 1 20000000 7 0 7058959 12 1 828127127732 ``` 输出： ``` 765443 10 544 6666 613579 987531 98765443210123456789 773737 210000000 70589590 8281271277321 ``` 请注意，示例中的输入和输出数据仅为展示格式，实际解决问题需要根据输入的具体数字来决定额外数字的插入位置。