给定字符串 $$$S$$$ 和 $$$T$$$,由小写英文字母组成。保证 $$$T$$$ 是字符串 abc 的排列。
查找字符串 $$$S'$$$,即 $$$S$$$ 按字典顺序排列的最小排列,使得 $$$T$$$ 不是 $$$S'$$$ 的子序列。
如果每个不同字符在两个字符串中出现的次数相同,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的排列。
如果可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得 $$$a$$$,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个字符串 $$$S$$$ ($$$1 \le |S| \le 100$$$),由小写英文字母组成。
每个测试用例的第二行包含一个字符串 $$$T$$$,它是字符串 abc 的排列。 (因此,$$$|T| = 3$$$)。
请注意,所有测试用例中 $$$|S|$$$ 的总和没有限制。
输出
对于每个测试用例,输出单个字符串 $$$S'$$$,即 $$$S$$$ 按字典顺序排列的最小排列,使得 $$$T$$$ 不是 $$$S'$$$ 的子序列。
示例
输入 #1
7 abacaba abc cccba acb dbsic bac abracadabra abc dddddddddddd cba bbc abc ac abc
输出 #1
aaaacbb abccc bcdis aaaaacbbdrr dddddddddddd bbc ac
注意
在第一个测试用例中,aaaabbc 和 aaaabcb 按字典顺序都小于 aaaacbb,但它们包含 abc 作为子序列。
在第二个测试用例中,abccc 是 cccba 的最小排列,并且不包含 acb 作为子序列。
在第三个测试用例中,bcdis 是 dbsic 的最小排列,并且不包含 bac 作为子序列。