You have two strings, $a$ and $\boldsymbol{b}$. Find a string, $\boldsymbol{\mathrm{~S~}}$, such that:

$\boldsymbol{\mathrm{~S~}}$ can be expressed as $s=s_{a}+s_{b}$ where $\boldsymbol{s_{a}}$ is a non-empty substring of $a$ and $s_{b}$ is a non-empty substring of $\boldsymbol{b}$.
$\boldsymbol{\mathrm{~S~}}$ is a palindromic string.
The length of $\boldsymbol{\mathrm{~S~}}$ is as long as possible.

For each of the $\textit{q}$ pairs of strings ($a_i$ and $b_i$) received as input, find and print string $s_i$ on a new line. If you're able to form more than one valid string $s_i$, print whichever one comes first alphabetically. If there is no valid answer, print $-1$ instead.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. The subsequent lines describe each query over two lines:

The first line contains a single string denoting $\boldsymbol{a}$.
The second line contains a single string denoting $\boldsymbol{b}$.

Constraints

$1\leq q\leq10$
$1\leq|a|,|b|\leq10^5$
$\boldsymbol{\alpha}$ and $\boldsymbol{b}$ contain only lowercase English letters.
Sum of |a| over all queries does not exceed $2\times10^5$
Sum of |b| over all queries does not exceed $2\times10^5$

Output Format

For each pair of strings ($a_i$ and $b_i$), find some $s_i$ satisfying the conditions above and print it on a new line. If there is no such string, print $-1$ instead.

Sample Input
3
bac
bac
abc
def
jdfh
fds

Sample Output
aba
-1
dfhfd

Explanation

We perform the following three queries:

Concatenate $s_a=\textbf{"a"}$ with $s_b=\text{"ba''}$ to create $s=\text{"aba"}$.
We're given $a=\text{"abc"}$ and $s_a=\text{"def"}$; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print $-1$.
Concatenate $s_a=\text{"dfh"}$ with $s_b=\text{"fd“}$ to create $s=\text{"dfhfd"}$. Note that we chose these particular substrings because the length of string $\boldsymbol{\mathrm{~S~}}$ must be maximal.

见题面

见题面