Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sasha, Misha & Their String Fight

Limits: 1s, 512 MB

Sasha loves strings. She always performs various operations on strings. One day while working on a string, she got an urgent call. So she just left it at home. When she returned , she was shocked to see her younger sister Misha had broken the string.

Not only that, Misha added random characters at random positions of the original string.

Now Sasha wants to restore the original string. Although it might be impossible because Misha might have thrown some characters into the dustbin.

But Misha is not entirely heartless! She left a clue for her sister so that Sasha can regain a sub-sequence of the original string. The clue is she didn’t change the order of characters (one or more) of the original string.

For example, “abcde” was Sasha’s string. Misha turned it into “fghbklmcjkdamneloa”. Sasha can’t get the whole string because Misha threw ‘a’ of Sasha’s string into the dustbin. But Sasha wants to regain as much as possible. So she can get “bcde” from Misha’s destruction.

Since you are senior programmer Sasha wants your help. Can you help her?

Input

The first line contains an integer T (1 ≤ T ≤ 100), denoting the number of test cases that follows.

Each test case contains two strings on a separate line. The first one is Sasha’s original string S (1 ≤ Length of S ≤ 1000). The second one is the string M (1 ≤ Length of M ≤ 1000) made by Misha by making changes to the original.

All characters of both strings are lowercase alphabets.

Output

Print the substring from M which might be the longest part of S. It’s guaranteed that answer will be unique for each test case.

Samples

InputOutput
3
abcde
fghbklmcjkdamneloa
abc
b
sasha
mibsbbcsdea
bcde
b
ssa

Discussion
Submit

Login to submit