Megumin, a talent explosion magic archwizard, spends a lot of time studying explosion magic spells. For two magic spells A and B, she found that she can combine them together to create a powerful magic spell. Moreover, if the last k characters of A matches the first k characters of B, they can be merged to obtain a more powerful spell. Megumin finds out that the shortest combination of the two spells has maximum power.
For example, if A = "xxxababa" and B = "babayyy", there are severals ways to combine them together:
"xxxababababayyy", by simply concatenating A and B, sharing no common characters.
"xxxabababayyy", by sharing "ba", the last 2 characters of A and the first 2 characters of B.
"xxxababayyy", by sharing "baba", the last 4 characters of A and the first 4 characters of B.
Among all ways of combination, "xxxababayyy" has the maximum power.
Given two magic spells A and B, please output the combination of A and B with maximum power.
Implementation Hints
Use strlen() to retrieve length of a string. Remember to #include <string.h>
Be careful when using strlen(), or your program might run slowly.
The first line is an integer T, meaning that the input has T test data. Each test data contains a single line.
In each test data, there are two magic spells A and B. Is is guaranteed that A and B only contains lower case alphabets (a-z).
Input consists of two lines. The first line contains A and the second line contains B. It is guaranteed that A and B only contains lower case alphabets (a-z).
1 <= T <= 10
1 <= |A|, |B| <= 1000
For each test data, please output the answer in one line. Remember to add new line character ('\n') in the end of each test data.