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.
import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
import java.io.*;

public class Codechef {
    public static void main(String[] args) throws java.lang.Exception {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        sc = new FastReader();
        int test = sc.nextInt();
        for (int z = 0; z < test; z++) {
            String s = sc.next();
            String t = sc.next();
            String new_S = "", new_T = "";
            int d = gcd(s.length(), t.length());
            //out.println("gcd : " + d);
            for (int i = 0; i < t.length() / d; i++) {
                new_S += s;
            }
            for (int i = 0; i < s.length() / d; i++) {
                new_T += t;
            }
            if (new_S.equals(new_T)) {
                out.println(new_S);
            }else {
                out.println(-1);
            }
        }
        out.close();
    }


    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    // method to return LCM of two numbers
    static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }

    public static FastReader sc;
    public static PrintWriter out;
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}