410043: GYM103931 E Expenditure Reduction

In order to make your money more abundant, rather than earning more it's much easier to reduce your expenditure.

Junpei is the manager of a membership restaurant. Due to the influences of the pandemic, the restaurant can not afford the excessively large menu of tasty dishes. It's then a problem to consider how to diminish the menu while keeping the specialties.

The menu can be viewed as a string $$$S$$$ containing only lowercase English letters and digits, and Junpei believes that the core feature of the restaurant is a string $$$F$$$ that is currently a subsequence of $$$S$$$. To reduce the menu, you can reduce $$$S$$$ to one of its substring $$$S'$$$, while keeping $$$F$$$ be the subsequence of $$$S'$$$. Junpei asks you to find the shortest substring $$$S'$$$ from $$$S$$$ that satisfies the requirement.

To those who may be curious about the definition of subsequence and substring, consider two non-empty strings $$$A, B$$$:

• If we say $$$A$$$ is a subsequence of $$$B$$$, we can find a set of $$$|A|$$$ indices $$$\{i_k\}$$$ where $$$1 \leq i_1 < i_2 < \dots < i_{|A|} \leq |B|$$$, such that $$$A = B_{i_1}B_{i_2}\dots B_{i_{|A|}}$$$.
• If we say $$$A$$$ is a substring of $$$B$$$, we can erase a (possibly empty) prefix and a (possibly empty) suffix from $$$B$$$ to obtain $$$A$$$.

The first line contains a single integer $$$T ~ (1 \leq T \leq 10^4)$$$, denoting the number of test cases.

For each test case, there's a single line containing two string $$$S, F ~ (1 \leq |S| \leq 10 ^ 5, 1 \leq |F| \leq 100)$$$ separated by a single space. It's guaranteed that $$$F$$$ is a subsequence of $$$S$$$, and both strings containing only lowercase English letters ('a' to 'z') and digits ('0' to '9').

It's guaranteed that the $$$\sum |S|$$$ of $$$T$$$ cases doesn't exceed $$$5 \times 10 ^ 5$$$.

For each test case, print one string in a single line denoting the shortest substring of $$$S$$$ containing $$$F$$$.

If there are multiple answers, print any of them.

4
114514 15
shanghaicpc ac
aaabbbaaabbbccc abc
howdeliciousandfreshitis oishii

145
aic
abbbc
owdeliciousandfreshiti