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 digit(c,present):
	if c=='A':
		if present=='i':
			return "5"
		else:
			return "0"
	elif c=='B':
		if present=='i':
			return "6"
		else:
			return "1"
	elif c=='C':
		if present=='i':
			return "7"
		else:
			return "2"
	elif c=='D':
		if present=='i':
			return "8"
		else:
			return "3"
	elif c=='E':
		if present=='i':
			return "9"
		else:
			return "4"									

def ans(s):
	l=len(s)
	present='i'
	count1=0
	ans1=digit(s[0],present)
	for i in xrange(l-1):
		if s[i]=='A':
			if present=='i':
				if s[i+1] in ['A','D','C']:
					if s[i+1]=='A':
						present='o'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
			else:
				if s[i+1] in ['A','E','B']:
					if s[i+1]=='A':
						present='i'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
		elif s[i]=='B':
			if present=='i':
				if s[i+1] in ['B','E','D']:
					if s[i+1]=='B':
						present='o'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
			else:
				if s[i+1] in ['B','A','C']:
					if s[i+1]=='B':
						present='i'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
		elif s[i]=='C':
			if present=='i':
				if s[i+1] in ['C','A','E']:
					if s[i+1]=='C':
						present='o'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
			else:
				if s[i+1] in ['C','B','D']:
					if s[i+1]=='C':
						present='i'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
		elif s[i]=='D':
			if present=='i':
				if s[i+1] in ['D','A','B']:
					if s[i+1]=='D':
						present='o'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
			else:
				if s[i+1] in ['D','E','C']:
					if s[i+1]=='D':
						present='i'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
		elif s[i]=='E':
			if present=='i':
				if s[i+1] in ['E','B','C']:
					if s[i+1]=='E':
						present='o'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
			else:
				if s[i+1] in ['E','A','D']:
					if s[i+1]=='E':
						present='i'
					ans1+=digit(s[i+1],present)
					count1+=1
				else:
					break
	present='o'				
	count2=0
	ans2=digit(s[0],present)				
	for i in xrange(l-1):
		if s[i]=='A':
			if present=='i':
				if s[i+1] in ['A','D','C']:
					if s[i+1]=='A':
						present='o'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
			else:
				if s[i+1] in ['A','E','B']:
					if s[i+1]=='A':
						present='i'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
		elif s[i]=='B':
			if present=='i':
				if s[i+1] in ['B','E','D']:
					if s[i+1]=='B':
						present='o'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
			else:
				if s[i+1] in ['B','A','C']:
					if s[i+1]=='B':
						present='i'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
		elif s[i]=='C':
			if present=='i':
				if s[i+1] in ['C','A','E']:
					if s[i+1]=='C':
						present='o'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
			else:
				if s[i+1] in ['C','B','D']:
					if s[i+1]=='C':
						present='i'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
		elif s[i]=='D':
			if present=='i':
				if s[i+1] in ['D','A','B']:
					if s[i+1]=='D':
						present='o'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
			else:
				if s[i+1] in ['D','E','C']:
					if s[i+1]=='D':
						present='i'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
		elif s[i]=='E':
			if present=='i':
				if s[i+1] in ['E','B','C']:
					if s[i+1]=='E':
						present='o'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
			else:
				if s[i+1] in ['E','A','D']:
					if s[i+1]=='E':
						present='i'
					ans2+=digit(s[i+1],present)
					count2+=1
				else:
					break
	if count1!=l-1 and count2!=l-1:
		return "-1"
	elif count1==l-1 and count2==l-1:
		return min(ans1,ans2)
	elif count1==l-1:
		return ans1
	return ans2			
t=input()
for test in xrange(t):
	s=raw_input()
	print ans(s)