CF1473B String LCM

Let'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.

The 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'.

For 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.

In the first test case, "baba" = "baba" $ \cdot~1~= $ "ba" $ \cdot~2 $ . In the second test case, "aaaaaa" = "aa" $ \cdot~3~= $ "aaa" $ \cdot~2 $ .