Problem: 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).

Solution (in PYTHON):

Solution:
s2 = ['AA', 'BB']
s2a = ['A', 'B']
s3 = ['ABA', 'BAB', 'AAB', 'BBA', 'BAA', 'ABB']
s3a = ['A', 'B', 'A', 'B', 'A', 'B']
t = int(raw_input())
for i in xrange(t):
    s = raw_input().upper()
    if len(s) == 2:
        if s in s2:
            print s2a[s2.index(s)]
        else:
            print -1
    elif len(s) == 3:
        if s in s3:
            print s3a[s3.index(s)]
        else:
            print -1
    else:
        if s[0] == 'A':
            s = 'B' + s
        else:
            s = 'A' + s
        if s[len(s) - 1] == 'A':
            s = s + 'B'
        else:
            s = s + 'A'
        n = len(s)
        if 'ABBA' in s or 'BAAB' in s:
            index = s.find('ABBA')
            if index < 0:
                index = s.find('BAAB')
            if index == 0:
                print s[1] + s[3 : n - 1]
            elif index == n - 4:
                print s[1 : n - 2]
            else:
                print s[1 : index + 2] + s[index + 3: n - 1]
        else:
            print -1