1473B. B. String LCM

CF1473B. String LCM

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

如果字符串 $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

样例输入 1

3
baba
ba
aa
aaa
aba
ab

样例输出 1

baba
aaaaaa
-1

提示

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

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