A. Запрещённая подпоследовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны строки $$$S$$$ и $$$T$$$, состоящие из строчных символов латинского алфавита. Гарантируется, что $$$T$$$ является перестановкой строки abc.

Найдите строку $$$S'$$$, которая является лексикографически минимальной перестановкой $$$S$$$, и при этом $$$T$$$ не является подпоследовательностью $$$S'$$$.

Строка $$$a$$$ является перестановкой строки $$$b$$$, если количество вхождений для всех различных символов одинаковое в обеих строках.

Строка $$$a$$$ является подпоследовательностью строки $$$b$$$, если $$$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'$$$.

Пример
Входные данные
7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc
Выходные данные
aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac
Примечание

В первом наборе входных данных и aaaabbc, и aaaabcb лексикографически меньше, чем aaaacbb, но они содержат abc как подпоследовательность.

Во втором наборе входных данных abccc является лексикографически минимальной перестановкой cccba и не содержит acb как подпоследовательность.

В третьем наборе входных данных bcdis является лексикографически минимальной перестановкой dbsic и не содержит bac как подпоследовательность.