E. Expenditure Reduction
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt i_2 \lt \dots \lt 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$$$.
Input

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$$$.

Output

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.

Example
Input
4
114514 15
shanghaicpc ac
aaabbbaaabbbccc abc
howdeliciousandfreshitis oishii
Output
145
aic
abbbc
owdeliciousandfreshiti