让我们定义一个字符串 $$$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(定义为 $$$LCM(s, t)$$$)是可被 $$$s$$$ 和 $$$t$$$ 整除的最短非空字符串。
给定两个字符串 $$$s$$$ 和 $$$t$$$。查找 $$$LCM(s, t)$$$ 或报告它不存在。可以证明,如果$$$LCM(s, t)$$$存在,则它是唯一的。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2000$$$) — 测试用例的数量。
每个测试用例由两行组成,包含字符串 $$$s$$$ 和 $$$t$$$ ($$$1 \le |s|, |t| \le 20$$$)。每个字符串中的每个字符都是“a”或“b”。
输出
对于每个测试用例,打印$$$LCM(s, t)$$$(如果存在);否则,打印-1。可以证明,如果$$$LCM(s, t)$$$存在,则它是唯一的。
示例
输入 #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$$$。