Hãy định nghĩa một phép nhân giữa một chuỗi a và một số nguyên dương x: a * x là một chuỗi kết quả của việc viết x bản sao của một chuỗi cái khác.

Ví dụ: "abc" * 2 = "abcabc", "a" * 5 = "aaaaa".

Chuỗi a chia hết cho chuỗi b nếu tồn tại số nguyên x sao cho b * x = a. Ví dụ: "abababab" chia hết cho "ab", nhưng không chia hết cho "ababab" hoặc "aa".

LCM của hai chuỗi s và t (được định nghĩa là LCM (s, t)) là chuỗi không rỗng ngắn nhất chia hết cho cả s và t.

Bạn được cung cấp hai chuỗi s và t. Tìm LCM (s, t) hoặc thông báo là không tìm được. Có thể chỉ ra rằng nếu tồn tại LCM (s, t) thì nó là duy nhất.

Input: STRLCM.INP

• Dòng đầu tiên chứa một số nguyên q (1 ≤ q ≤ 2000) – số truy vấn
• Mỗi trường hợp kiểm tra bao gồm hai dòng, chứa các chuỗi s và t (1 ≤ |s|, |t| ≤ 200). Mỗi ký tự trong mỗi chuỗi này là 'a' hoặc 'b'.

Output: STRLCM.OUT

• Đối với mỗi truy vấn, in LCM (s, t) nếu nó tồn tại; nếu không, in -1. Có thể chỉ ra rằng nếu tồn tại LCM (s, t) thì nó là duy nhất.