The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:





	Let's consider a walk W in graph G, which consists of L vertices W1, W2, ..., WL, such that Wi is connected with Wi + 1 for 1 ≤ i < L. A string S of L letters 'A'-'E' is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.

For example, S = 'ABBECCD' is realized by W = (0, 1, 6, 9, 7, 2, 3).
Your task is to determine whether there is a walk W which realizes a given string S in graph G, and if so, find the lexicographically least such walk.

Input

	The first line of the input contains one integer T denoting the number of testcases to process.


	The only line of each testcase contains one string S. It is guaranteed that S only consists of symbols 'A'-'E'.


Output

	The output should contain exactly T lines, one line per each testcase in the order of their appearance. For each testcase, if there is no walk W which realizes S, then output -1. Otherwise, you should output the least lexicographical walk W which realizes S. Since all of the vertices are numbered from 0 to 9, then it can be encoded as a string consisting of symbols '0'-'9' (see the "Examples" section for more details).


Constraints
1 ≤ T ≤ 8;
1 ≤ |S| ≤ 100000(10^5).

Examples
Input:
2
AAB
AABE

Output:
501
-1
def p(s):
	print "".join(map(str,s))
def f(i):
	op = []
	if i == 'a': return 0
	if i == 'b': return 1
	if i == 'c': return 2
	if i == 'd': return 3 
	if i == 'e': return 4
	if i == 'A': return 5
	if i == 'B': return 6
	if i == 'C': return 7
	if i == 'D': return 8
	if i == 'E': return 9


T = input()
d = {
		'a':['e', 'b', 'A'],
		'b':['a', 'c', 'B'],
		'c':['b', 'd', 'C'],
		'd':['c', 'e', 'D'],
		'e':['d', 'a', 'E'],
		'A':['C', 'D', 'a'],
		'B':['D', 'E', 'b'],
		'C':['E', 'A', 'c'],
		'D':['A', 'B', 'd'],
		'E':['B', 'C', 'e']
	}
while T > 0:
	T -= 1
	s = raw_input()
	i = 1
	l = []
	l.append(f(s[0].lower()))
	while i < len(s):
		x = f(s[i])
		y = f(s[i].lower())
		
		if l[-1] < 5:
			if x == l[-1] + 5:
				l.append(x)
			elif y == (l[-1]+1) % 5 or y == (l[-1]-1) %5:
				l.append(y)
			else: break
		
		else:
			if y == l[-1] - 5:
				l.append(y)
			elif abs(l[-1]-x) == 2 or abs(l[-1]-x) == 3:
				l.append(x)
			else: break

		i += 1
	if len(l) == len(s):
		p(l)
	else:
		i = 1
		l = []
		l.append(f(s[0]))
		while i < len(s):
			x = f(s[i])
			y = f(s[i].lower())
			
			if l[-1] < 5:
				if x == l[-1] + 5:
					l.append(x)
				elif y == (l[-1]+1) % 5 or y == (l[-1]-1) %5:
					l.append(y)
				else: break
			
			else:
				if y == l[-1] - 5:
					l.append(y)
				elif abs(l[-1]-x) == 2 or abs(l[-1]-x) == 3:
					l.append(x)
				else: break

			i += 1
		if len(l) == len(s):
			p(l)
		else:
			print -1