B. LCM строк
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Давайте определим операцию умножения между строкой $$$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$$$.