← 返回比赛

已结束 GESP欢乐赛 #6

← 上一题下一题 →

A1457 | $最短公倍串$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

狗星的字符串乘法是这样定义的：给定一个字符串 $s$ 和一个整数 $x$，则 $a \times x$ 等于 $x$ 个字符串 $a$ 拼接。例如：$s =$ abc，$x = 2$，$s$ $\times$ $x =$ abcabc 。b $\times 5 =$ bbbbb。 如果存在一个整数 $x$，使得 $s \times x = s1$，就称字符串 $s1$ 被字符串 $s$ 整除。例如：ababab 可以被 ab 整除，不能被 aba 或 aa 整除。 两个字符串的最短公倍串（$lcm(s,s1)$）是指可以被 $s$ 和 $s1$ 整除的最短非空字符串。 $AC$ 狗得到两个字符串 $s$ 和 $s1$，请帮它找出 $lcm(s,s1)$。可以证明对于 $s$ 和 $s1$ ，$lcm(s,s1)$ 是唯一的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2000$) — 测试用例的数量。 每个测试用例由一行组成，包含字符串 $s$ 和 $s1$ ($1 \le | s| , |s1| \le 20$)。 字符串中的每个字符由 a、 b组成。

输出格式

对于每个测试用例，如果 $lcm(s，s1)$ 存在，则打印 $lcm(s，s1)$；否则打印 -1 。

输入输出样例

输入 #1

3
baba ba
aa aaa
aba ab

输出 #1

baba
aaaaaa
-1

C++ 编辑器

输入

输出