DISH

Time limit2sMemory limit512 MB

Summary

For each pair of strings, output a shortest string that contains both input strings as substrings.

Level: Medium6 of 10
Topics: String, Dynamic programming, Shortest path, String matching
Solved: No attempts yet

Problem

A restaurant in Kabul wants to create new foods by combining multiple foods. When displaying the menu, the restaurant wants to name each of these foods so that customers can learn about it with the least explanation.

The head of the restaurant decided to use the shortest string that contains the main meal names as substrings in the new name. For example, "shrimpce" is the name of a dish created by combining "rice" and "shrimp", and no shorter string has the same property. Write a program that calculates the shortest name for the foods of these dishes.

Input

The first line contains $N$ , the number of test cases. Each of the next $N$ lines contains two strings, which represent the names of the foods to be combined. All names have a maximum length of 100 and consist only of alphabetic characters.

Output

For each test case, output the shortest name of the resulting food on one line. If more than one shortest name is possible, any one of them is acceptable.

Examples1

Example 1

Input

3
spaghetti salad
chicken cheese
ananas banana

Expected output

spaghettilad
chickenese
bananas