題意

ある文字列s,tが与えられる
ここで、ある文字列strを考えたときに、別の文字列aをb回繰り返してstrが得られるとき、strはaで割り切れるとする。
- 例えば、abababはab x 3回なので、abで割り切れ、 ababab x 1回なので、abababで割り切れる
- 例えば、abcはabc x 1回でしか割り切れないので、abcでのみ割り切れる
s,tで割り切れる最小の文字列を答えよ。存在しない場合は-1を出力せよ。

こう考えた

考察は解説に任せます、この問題は文字列のLCM(一般的なものではなく、この問題の範囲の中での言葉です)を求める問題です。
上記例のようにこの問題は、整数の約数のように考えられます。文字札s,tに共通に含まれる共有の約文字列(約数のようなもの)を求め、それぞれの個数のLCMを求めた回数繰り返す。

ポイント：ある文字列の約文字列（約数)の求め方

さて、この動作に必要なのは、以下のような情報を列挙することです。

abababはab x 3回なので、abで割り切れ、 ababab x 1回なので、abababで割り切れる
abcはabc x 1回でしか割り切れないので、abcでのみ割り切れる
以下のように考えます。
あるn文字の文字列の1文字目からi文字目($1\leq i \leq n$)文字目を使って、元の文字列が作れるかを判定する
この際、nがiで割り切れなければ、その文字列をつなげて作成できるものではないので候補にはならない
- abababはababをマッチングの方法によっては2回含みますが、この問題の題意では、1回含むなら、abab ２回含むならababababになるので、ababからabababを作ることはd系ません
i文字の文字だけで構成される可能性があるなら、元の文字列の1～i文字目, i+1 ～ 2i文字目 , ... , ki+1 ～ n 文字目にその文字が含まれるかを確認する

ここで、Zアルゴリズムを使います。

iをnまでインクリメントさせながら、1-i文字目までと元の文字列を連結した文字列にZアルゴリズムを適応する
得られた配列を元の文字列の1文字目からstep iで回し、i以上であることを確認する
すべてのforでi以上なら、その文字は1からi文字目までの繰り返しでできている。失敗すれば、1からi文字目までの繰り返しでその文字列を作ることはできない

実装

class zAlgorithm():
    def __init__(self, s):
        self.sdat = list(map(lambda x: ord(x), s))
        self.sl = len(s)
        self.res = [0] * self.sl
        self.res[0] = self.sl
        i, j = 1, 0
        while i < self.sl:
            while (i+j) < self.sl:
                if self.sdat[j] != self.sdat[i+j]:
                    break
                j += 1
            self.res[i] = j
            if(j == 0):
                i += 1
                continue
            k = 1
            while (i+k) < self.sl and (k+self.res[k] < j):
                self.res[i+k] = self.res[k]
                k += 1
            i += k
            j -= k
def stringDivisors(s):
    z = zAlgorithm(s)
    res = dict()
    for i in range(len(s) // 2):
        curTryLen = i+1
        if len(s) % curTryLen != 0:
            continue
        target = s[:i+1]
        t = s[:i+1] + ":" + s
        z = zAlgorithm(t)
        can = True
        for j in range(0, len(s) , curTryLen):
            if z.res[len(target) + 1 + j] >= len(target):
                continue
            can = False
            break
        if can:
            res[target] = len(s) // curTryLen
    res[s] = 1
    return res
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
q = int(input())
for _ in range(q):
    s, t = input(), input()
    sdiv = stringDivisors(s)
    tdiv = stringDivisors(t)
    reslen = 0
    resval = ""
    for k in list(sdiv.keys()):
        if k not in tdiv:
            continue
        tmps = str(k) * lcm(sdiv[k], tdiv[k])
        if len(tmps) > reslen:
            reslen = len(tmps)
            resval = tmps
    if resval == "":
        print(-1)
    else:
        print(resval)