B. String LCMtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's define a multiplication operation between a string a and a positive integer x: a \cdot x is the string that is a result of writing x copies of a one after another. For example, "abc" \cdot~2~= "abcabc", "a" \cdot~5~= "aaaaa".A string a is divisible by another string b if there exists an integer x such that b \cdot x = a. For example, "abababab" is divisible by "ab", but is not divisible by "ababab" or "aa".LCM of two strings s and t (defined as LCM(s, t)) is the shortest non-empty string that is divisible by both s and t.You are given two strings s and t. Find LCM(s, t) or report that it does not exist. It can be shown that if LCM(s, t) exists, it is unique.InputThe first line contains one integer q (1 \le q \le 2000) — the number of test cases.Each test case consists of two lines, containing strings s and t (1 \le |s|, |t| \le 20). Each character in each of these strings is either 'a' or 'b'.OutputFor each test case, print LCM(s, t) if it exists; otherwise, print -1. It can be shown that if LCM(s, t) exists, it is unique.ExampleInput
3
baba
ba
aa
aaa
aba
ab
Output
baba
aaaaaa
-1
NoteIn the first test case, "baba" = "baba" \cdot~1~= "ba" \cdot~2.In the second test case, "aaaaaa" = "aa" \cdot~3~= "aaa" \cdot~2.
3
baba
ba
aa
aaa
aba
ab

baba aaaaaa -1 
['brute force', 'math', 'number theory', 'strings', '*1000']