Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

math

number theory

strings

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. String LCM

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet's define a multiplication operation between a string $$$a$$$ and a positive integer $$$x$$$: $$$a \cdot x$$$ is the string that is a result of writing $$$x$$$ copies of $$$a$$$ one after another. For example, "abc" $$$\cdot~2~=$$$ "abcabc", "a" $$$\cdot~5~=$$$ "aaaaa".

A string $$$a$$$ is divisible by another string $$$b$$$ if there exists an integer $$$x$$$ such that $$$b \cdot x = a$$$. For example, "abababab" is divisible by "ab", but is not divisible by "ababab" or "aa".

LCM of two strings $$$s$$$ and $$$t$$$ (defined as $$$LCM(s, t)$$$) is the shortest non-empty string that is divisible by both $$$s$$$ and $$$t$$$.

You are given two strings $$$s$$$ and $$$t$$$. Find $$$LCM(s, t)$$$ or report that it does not exist. It can be shown that if $$$LCM(s, t)$$$ exists, it is unique.

Input

The first line contains one integer $$$q$$$ ($$$1 \le q \le 2000$$$) — the number of test cases.

Each test case consists of two lines, containing strings $$$s$$$ and $$$t$$$ ($$$1 \le |s|, |t| \le 20$$$). Each character in each of these strings is either 'a' or 'b'.

Output

For each test case, print $$$LCM(s, t)$$$ if it exists; otherwise, print -1. It can be shown that if $$$LCM(s, t)$$$ exists, it is unique.

Example

Input

3 baba ba aa aaa aba ab

Output

baba aaaaaa -1

Note

In the first test case, "baba" = "baba" $$$\cdot~1~=$$$ "ba" $$$\cdot~2$$$.

In the second test case, "aaaaaa" = "aa" $$$\cdot~3~=$$$ "aaa" $$$\cdot~2$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2023 14:22:45 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|