1473_B. String LCM
Let's define a multiplication operation between a string a and a positive integer x: a ⋅ x is the string that is a result of writing x copies of a one after another. For example, "abc" ⋅~2~= "abcabc", "a" ⋅~5~= "aaaaa".

A string a is divisible by another string b if there exists an integer x such that b ⋅ 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 ≤ q ≤ 2000) — the number of test cases.

Each test case consists of two lines, containing strings s and t (1 ≤ |s|, |t| ≤ 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" ⋅~1~= "ba" ⋅~2.

In the second test case, "aaaaaa" = "aa" ⋅~3~= "aaa" ⋅~2.
```python
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b % a, a)
 
# Function to return LCM of two numbers
def compute_lcm(a,b):
    return (a / gcd(a,b))* b

def main():
    T = int(input())
    for c in range(T):
        s1 = input().rstrip()
        s2 = input().rstrip()
        
        s = s1 if len(s1) <= len(s2) else s2
        l = s2 if len(s1) <= len(s2) else s1
        
        bs = [0 for i in range(len(s))]
        bl = [0 for i in range(len(l))]
        
        pl = 0
        
        res = True
        
        while True:
            ps = 0
            bl[pl] = 1
            while ps < len(s):
                if s[ps] != l[pl]:
                    res = False
                    break
                ps += 1
                pl = (pl + 1) % len(l)
            if res == False:
                break
            if bl[pl] == 1:
                res = (pl == 0)
                break
        
        if res == False:
            print("-1")
        else:
            lcm = compute_lcm(len(s), len(l))
            ans = ""
            for c in range(int(lcm/len(s))):
                ans += s
            print(ans)
        
        
            

main()
```