Ta đị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 được hình thành bằng cách sao chép \(x\) lần chuỗi \(a\).

Ví dụ: abc\(.2\) = abcabc, a\(.5\) = aaaaa.

Một chuỗi \(a\) được gọi là chia hết cho chuỗi \(b\) nếu tồn tại một số nguyên \(x\) sao cho \(b.x\) = \(a\).

Ví dụ abababab chia hết cho chuỗi ab, nhưng không chia hết cho ababab hoặc a.

\(LCM\) của hai chuỗi \(s\) và \(t\) là chuỗi ngắn nhất khác rỗng sao cho chuỗi \(s\) và chuỗi \(t\) chia hết cho chuỗi đó.

Bạn được cho hai chuỗi \(s\) và \(t\). Hãy tìm \(LCM(s, t)\).

Input

• Dòng đầu tiên gồm một số nguyên \(q\) (\(1\leq q \leq 2000\)) là số lượng test case.
• Mỗi test case gồm hai dòng, chứa hai chuỗi \(s\) và \(t\) (\(1 \leq |s|, |t| \leq 20\)). Mỗi kí tự trong chuỗi là một trong hai kí tự a hoặc b.

Output

• Với mỗi test case, in ra bội chung nhỏ nhất \(LCM(s, t)\) nếu tồn tại, ngược lại in ra -1.

Example

3
baba
ba
aa
aaa
aba
ab

baba
aaaaaa
-1