You are given a uniformly randomly generated string S, consisting of letters from the set {"A", "B"}. Your task is to find a string T that appears in S as a subsequence exactly twice.
In other words, you need to find such a string T, that there exist exactly two sets of indexes i1, i2, ..., i|T| and j1, j2, ..., j|T| such that there exists some k, where ik ≠ jk and S{i1...i|T|} = S{j1...j|T|} = T.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single string S.
The string S was generated randomly. For a generating string S, we first choose an integer N denoting a length of S. After that every symbol of the string S is chosen randomly from the set {"A", "B"} and the both symbols have equal probability to be chosen. Note that N is not choosen randomly.

Output
For each test case, output a string that occurs exactly twice as a subsequence in S, or output -1 if there is no such string. If there are more than one possible subsequences occurring exactly two times, you can print any one of them.

Constraints

1 ≤ T ≤ 10

Example
Input:
2
AAAA
BAB

Output:
-1
B

Explanation
Test case #1:

The string "AAAA" appears once as a subsequence in itself.
The string "AAA" appears four times as a subsequence in "AAAA"; possible positions: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}.
The strings "AA" and "A" also appear in "AAAA" as a subsequence strictly more than twice.

So, there is no string of "AAAA", which appears exactly twice. Hence answer is -1.
Test case #2: Two occurrences of "B" in "BAB" are {1} and {3} (1-based indexing).

见题面

见题面