Công ty Trái cây thế kỷ 21 chuyên tạo ra các loại trái cây mới bằng cách chuyển gen từ một loại trái cây sang bộ gen của một loại trái cây khác. Hầu hết các phương pháp này không hiệu quả, nhưng đôi khi, trong những trường hợp rất hiếm, một loại trái cây mới xuất hiện có vị giống như một hỗn hợp giữa cả hai.

Một chủ đề thảo luận lớn trong công ty là Những sáng tạo mới nên được gọi như thế nào? Dĩ nhiên, hỗn hợp giữa táo và lê có thể được gọi là lê, nhưng điều này nghe có vẻ không thú vị lắm. Ông chủ cuối cùng quyết định sử dụng chuỗi ngắn nhất chứa cả tên của các loại trái cây ban đầu làm tên mới. Ví dụ: applear chứa apple và pear (APPLEar và apPlEAR) và không có chuỗi nào ngắn hơn có cùng thuộc tính.

Do đó, một sự kết hợp của một quả cranberry và một boysenberry sẽ được gọi là boysecranberry hoặc craboysenberry. Công việc của bạn là viết một chương trình tính toán một tên ngắn nhất như vậy cho sự kết hợp của hai loại trái cây nhất định.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) - là số lượng trường hợp thử nghiệm \((T \le 10)\)
• Mỗi dòng tiếp theo của tệp đầu vào chứa hai chuỗi đại diện cho tên của hai loại trái cây được kết hợp. Tất cả các tên có độ dài tối đa là \(300\) và chỉ bao gồm các ký tự chữ cái.

Dữ liệu ra

• Đối với mỗi trường hợp thử nghiệm, xuất tên ngắn nhất của quả thu được trên một dòng. Nếu có nhiều hơn một tên ngắn nhất có thể, bất kỳ tên nào cũng được chấp nhận.

Input 1

3
apple peach
ananas banana
pear peach

Output 1

appleach
bananas
pearch