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.

我们定义字符串 $a$ 与正整数 $x$ 之间的乘法运算：$a \cdot x$ 表示将 $a$ 重复书写 $x$ 次所得到的字符串。例如，"abc" $\cdot~2~=$ "abcabc"，"a" $\cdot~5~=$ "aaaaa"。

若存在整数 $x$，使得 $b \cdot x = a$，则称字符串 $a$ 可被字符串 $b$ 整除。例如，"abababab" 可被 "ab" 整除，但不能被 "ababab" 或 "aa" 整除。

两个字符串 $s$ 和 $t$ 的最小公倍式（记为 $LCM(s, t)$）是指最短的非空字符串，它同时可被 $s$ 和 $t$ 整除。

给定两个字符串 $s$ 和 $t$，请找出 $LCM(s, t)$；若不存在，则报告不存在。可以证明：若 $LCM(s, t)$ 存在，则其唯一。

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

第一行包含一个整数 $q$（$1 \le q \le 2000$）—— 表示测试用例的数量。

每个测试用例由两行组成，分别包含字符串 $s$ 和 $t$（$1 \le |s|, |t| \le 20$）。这两个字符串中的每个字符均为 'a' 或 '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.

对于每个测试用例，如果 $LCM(s, t)$ 存在，则输出 $LCM(s, t)$；否则输出 -1。可以证明：若 $LCM(s, t)$ 存在，则其唯一。

In the first test case, "baba" = "baba" $\cdot~1~=$ "ba" $\cdot~2$.

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

在第一个测试用例中，“baba” = “baba” $\cdot~1~=$ “ba” $\cdot~2$。

在第二个测试用例中，“aaaaaa” = “aa” $\cdot~3~=$ “aaa” $\cdot~2$。