题目描述

小美是一个数学爱好者，他经常思考各种数字之间的奥秘。今天，他想要解决一个有趣的问题：如何在一个数字中插入一个数字，以得到最大的结果？

他发现这个问题很有挑战性，因为他必须找到一种方法，能够在给定的数字中插入一个数字，使得插入后的结果最大。于是，他开始思考并设计了一种算法来解决这个问题。

算法的核心思想是：首先将第一个数字转化为字符串，然后将第二个数字插入到字符串的不同位置，得到多个可能的结果。最后，从中选择最大的一个数字作为最终的结果。

小美已经写好了这个算法，并请你帮忙测试一下。请编写一个程序，输入小美手上的两个数字，输出插入后得到的最大数字。(前导零正常输出)

输入描述

输入第一行为一个数字$T$，表示有$T$组测试样例

接下来的$T$行对于每一组数据，包含一行有 $2$个空格隔开的整数，表示任意正整数 $a$ 和待插入的数字 $b$，

$1$ $\leq$ $T$ $\leq$ $10$, 1 $\leq$ $a$ $\leq$ $10 ^{50000}$ , $0$ $\leq$ $b$ $\leq$ $9$

输出描述

对于每组数据，输出一行，包括一个整数，得到最大的整数。

样例

输入

5
123456 8
58264 2
44 5
10086 0
8 0

输出

8123456
582642
544
100860
80

题目思路

思路：贪心

插入一个数字后，其代替原有位置的数，要使得新的数的值越大。

原数 $a$ 的长度为 $n$ ，数的索引从 $1$ 开始，假设插入的位置为 $k$，即插入后，组成为：$[1, k] + number + [k, n]$

数 $number$ 有两种插入的位置：