You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目思路

思路：贪心

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

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

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

小莫正在整理一批奖券，每张奖券上有一个由数字组成的原始编号。活动规则允许他为每个编号在任意位置添加一个额外的数字，从而形成一个新编号。小莫希望新编号尽可能大（按数值比较，允许出现前导零）。请你帮他求出，对于每个原始编号和给定的额外数字，能得到的最大编号是什么。

保证测试数据组数 $T \le 10$ ，原始编号的长度不超过 $50000$ ，额外数字 $c$ 是 $0$ 到 $9$ 的数字字符。

第一行包含一个整数 $T$ （ $1 \le T \le 10$ ），表示测试数据组数。接下来 $T$ 行，每行包含两个用空格分隔的值：一个由数字组成的字符串 $S$ 和一个数字字符 $c$ ，分别表示原始编号和待添加的额外数字。

对于每组数据，输出一行，包含一个字符串，表示添加后得到的最大编号。

输入

输出

975431
535427
00

说明

第一组：原始编号为 97531，额外数字为 4。从左向右扫描，第一个小于 4 的数字是 3（位于第 4 位），因此将 4 插入到 3 之前，得到最大编号 975431。

第二组：原始编号为 35427，额外数字为 5。扫描时发现第一个数字 3 已经小于 5，所以直接将 5 插入到开头，得到 535427，这是可能形成的最大编号。

第三组：原始编号为 0，额外数字为 0。由于 0 不小于 0，扫描结束后未找到更小的数字，按规则将 0 添加到末尾，得到 00。题目允许前导零，用数值比较时 00 不小于 0，这是该情况下能得到的最大编号。