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:
for t in xrange(int(raw_input())):
	s = raw_input()
	n = len(s)
	a = s.count('A')
	b = n-a 
	if (a==2):
		print "A"
	elif (b==2):
		print "B"
	elif (n<4):
		print -1
	else:
		if (s[0]=="A"):
			s = "B"+s
		else:
			s = "A"+s
		if (s[-1]=="A"):
			s = s+"B"
		else:
			s = s+"A"
		pos1 = s.find("ABBA")
		pos2 = s.find("BAAB")
		if (pos1 == -1 and pos2 == -1):
			print -1
		else:
			if (pos1 == -1):
				pos = pos2
			elif (pos2 == -1):
				pos = pos1
			else:
				pos = min(pos1, pos2)
			print s[1:pos+1]+s[pos+2:-1]