题目描述

给定一个长度为 $n$ 的正数和一个额外数字，你可以把这个数字插入到那个正数的任何位置，包括它的开头和结尾。你的任务是让结果尽可能的大。

例如，给定数字 $76543$，额外数字是 $4$，则你可以得到的最大结果为 $765443$。它可以通过两种方式获得 —— 在 $76543$ 的第 $3$ 位或第 $4$ 位之后插入数字 $4$。

输入格式

第一行输入数据组数 $t\ (1 \leq t \leq 10^4)$。测试样例描述如下：

样例第一行为两个整数 $n$ 和 $d\ (1 \le n \le 2 \times 10^5,\ 0 \le d \le 9)$，分别代表数字长度和额外数字。

样例第二行是一个长度为 $n$ 的数字串，代表你最初拥有的数字。数据保证此数字不含有前导零。

输出格式

对于每一组样例，输出一个长度为 $n + 1$ 的数字串，代表能得到的最大数字。

（Traslated by Leirt_Abu）

样例

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