18401번 - DISH 다국어

A restaurant in Kabul is very interested to create new food by combining multiple foods. They want to name each of these foods in a way so that customers can learn about it with the least explanation when displaying the menu.

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

The first input line contains N, the number of test cases. The next N line, each contains two strings that represent the names of the foods that should be combined. All names have a maximum length of 100 and only consist of alphabetic characters.

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 is acceptable.