Tên trái cây lai

Một hãng nông sản lai tạo giống trái cây mới từ hai giống cũ, và muốn đặt tên cho giống mới sao cho tên của cả hai giống cũ đều xuất hiện trong đó dưới dạng xâu con (xoá bớt một số ký tự vẫn giữ nguyên thứ tự thì thu được tên cũ). Ví dụ mangorange không phải lựa chọn tốt, còn morangeo chứa được cả mango lẫn orange.

Với mỗi cặp tên cho trước, hãy tìm tên ngắn nhất thoả mãn. Nếu có nhiều tên ngắn nhất, chọn tên nhỏ nhất theo thứ tự từ điển.

Input

• Dòng đầu tiên chứa số nguyên \(T\) - số cặp tên.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai xâu cách nhau bởi một dấu cách là tên của hai giống trái cây.

Output

Với mỗi cặp, in ra một dòng là tên ngắn nhất chứa cả hai tên (nhỏ nhất theo thứ tự từ điển nếu có nhiều).

Constraints

• \(1 \le T \le 10\)
• Mỗi tên dài từ \(1\) đến \(300\) ký tự và chỉ gồm chữ cái tiếng Anh viết thường.

Sample Input

3
mango orange
lemon melon
kiwi kiwi

Sample Output

morangeo
lemelon
kiwi

Explanation

mango và orange có xâu con chung dài nhất là ang (độ dài \(3\)), nên tên ngắn nhất có độ dài \(5 + 6 - 3 = 8\). Hai tên trùng nhau thì tên mới chính là tên đó.