You have two strings, and . Find a string, , such that:
- can be expressed as where is a non-empty substring of and is a non-empty substring of .
- is a palindromic string.
- The length of is as long as possible.
For each of the pairs of strings ( and ) received as input, find and print string on a new line. If you're able to form more than one valid string , print whichever one comes first alphabetically. If there is no valid answer, print instead.
Input Format
The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query over two lines:
- The first line contains a single string denoting .
- The second line contains a single string denoting .
Constraints
- and contain only lowercase English letters.
- Sum of |a| over all queries does not exceed
- Sum of |b| over all queries does not exceed
Output Format
For each pair of strings ( and ), find some satisfying the conditions above and print it on a new line. If there is no such string, print instead.
Sample Input
3
bac
bac
abc
def
jdfh
fds
Sample Output
aba
-1
dfhfd
Explanation
We perform the following three queries:
- Concatenate with to create .
- We're given and ; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print .
- Concatenate with to create . Note that we chose these particular substrings because the length of string must be maximal.