您有一个长度为 $$$n$$$ 的正数和一位附加数字。
您可以在号码中的任意位置插入该数字,包括开头或结尾。
你的任务是使结果尽可能大。
例如,您的号码为 $$$76543$$$,附加数字为 $$$4$$$。那么你能得到的最大数字是$$$765443$$$,可以通过两种方式获得——在数字的第$$$3$$$后面或第$$$4$$$数字后面插入一个数字。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例描述的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le d \le 9$$$) — 分别是数字的长度和附加数字。
每个测试用例描述的第二行包含一个由 $$$n$$$ 数字组成的字符串 - 您最初拥有的数字。确保该数字不包含前导零。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个由 $$$n + 1$$$ 数字组成的字符串 - 可以获得的最大可能数字。
示例
输入 #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
输出 #1
765443 10 544 6666 613579 987531 98765443210123456789 773737 210000000 70589590 8281271277321