Давайте определим операцию умножения между строкой $$$a$$$ и положительным целым числом $$$x$$$: $$$a \cdot x$$$ — это строка, которая является результатом записи $$$x$$$ копий $$$a$$$ одна за другой. Например, «abc» $$$\cdot~2~=$$$ «abcabc», «a» $$$\cdot~5~=$$$ «aaaaa».
Строка $$$a$$$ делится на другую строку $$$b$$$, если существует целое число $$$x$$$ такое, что $$$b \cdot x = a$$$. Например, «abababab» делится на «ab», но не делится на «ababab» или «aa».
LCM из двух строк $$$s$$$ и $$$t$$$ (определяется как $$$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)$$$ существует, то он единственный.
3 baba ba aa aaa aba ab
baba aaaaaa -1
В первом примере «baba» = «baba» $$$\cdot~1~=$$$ «ba» $$$\cdot~2$$$.
Во втором примере, «aaaaaa» = «aa» $$$\cdot~3~=$$$ «aaa» $$$\cdot~2$$$.
