String LCM

题意翻译

**题目描述** 如果字符串 $s$ 可以变成 $n$ 个字符串 $s_1$ 首尾相连，则说 $s$ 能被 $s_1$ 整除或 $s_1$ 能整除 $s$。 定义两个字符串 $s_1,s_2$ 的最短公倍串为：**可以被 $s_1$ 和 $s_2$ 整除的最短的非空串**。 例如： $baba$ 和 $ba$ 的最短公倍串为 $baba$；$aa$ 和 $aaa$ 的最短公倍串为 $aaaaaa$；$aba$ 和 $ab$ 没有最短公倍串。 **输入格式** 第一行一个整数 $t(1 \leq t \leq 2000)$，表示测试数据组数。 对于每一个测试数据，一共两行，每行一个字符串 $s_1,s_2(1 \leq |s_1|,|s_2| \leq 20)$，两个字符串都由 $'a'$ 和 $'b'$ 组成。 **输出格式** 对于每一个测试数据，输出 $s_1,s_2$ 的最短公倍串，如果没有输出 $-1$。 translated by [me](https://www.luogu.com.cn/user/390770)

题目描述

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.

输入输出样例

输入样例 #1

3
baba
ba
aa
aaa
aba
ab

输出样例 #1

baba
aaaaaa
-1

说明

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