CF1617A.Forbidden Subsequence

You are given strings $S$ and $T$, consisting of lowercase English letters. It is guaranteed that $T$ is a permutation of the string abc.

Find string $S'$, the lexicographically smallest permutation of $S$ such that $T$ is not a subsequence of $S'$.

String $a$ is a permutation of string $b$ if the number of occurrences of each distinct character is the same in both strings.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

给定两个字符串 $S$ 和 $T$，均由小写英文字母组成。保证 $T$ 是字符串 abc 的一个排列。

请找出字符串 $S'$，它是 $S$ 的字典序最小的排列，且满足 $T$ 不是 $S'$ 的子序列。

若两个字符串中每个不同字符的出现次数均相同，则称字符串 $a$ 是字符串 $b$ 的一个排列。

若字符串 $a$ 可通过从字符串 $b$ 中删除若干（可能为零个或全部）字符得到，则称字符串 $a$ 是字符串 $b$ 的一个子序列。

当且仅当以下任一条件成立时，字符串 $a$ 字典序小于字符串 $b$：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀且 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中先于 $b$ 中对应位置的字母。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a string $S$ ($1 \le |S| \le 100$), consisting of lowercase English letters.

The second line of each test case contains a string $T$ that is a permutation of the string abc. (Hence, $|T| = 3$).

Note that there is no limit on the sum of $|S|$ across all test cases.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个字符串 $S$（$1 \le |S| \le 100$），由小写英文字母组成。

每个测试用例的第二行包含一个字符串 $T$，它是字符串 abc 的一个排列。（因此，$|T| = 3$。）

注意：所有测试用例的 $|S|$ 总和没有限制。

For each test case, output a single string $S'$, the lexicographically smallest permutation of $S$ such that $T$ is not a subsequence of $S'$.

对于每个测试用例，输出一个字符串 $S'$，它是 $S$ 的字典序最小的排列，且 $T$ 不是 $S'$ 的子序列。

In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence.

In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence.

In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.

在第一个测试用例中，aaaabbc 和 aaaabcb 都字典序小于 aaaacbb，但它们都包含 abc 作为子序列。

在第二个测试用例中，abccc 是 cccba 的最小排列，且不包含 acb 作为子序列。

在第三个测试用例中，bcdis 是 dbsic 的最小排列，且不包含 bac 作为子序列。