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
t=input()
connection=[[1,4,5],[0,2,6],[1,3,7],[2,4,8],[0,3,9],[0,7,8],[8,9,1],[5,9,2],[5,6,3],[6,7,4]]
for i in range(t):
    a=raw_input()
    ans=""
    count=0
    current=ord(a[count])-ord('A')
    ans+=str(current)
    while count<len(a)-1 and ((ord(a[count+1])-ord('A') in connection[current]) or (ord(a[count+1])-ord('A')+5 in connection[current])):
        count+=1
        if (ord(a[count])-ord('A') in connection[current]):
            current=ord(a[count])-ord('A')
        else:
            current=ord(a[count])-ord('A')+5
        ans+=str(current)
    if count==len(a)-1:
        print ans
        continue
    ans=""
    count=0
    current=ord(a[count])-ord('A')+5
    ans+=str(current)
    while count<len(a)-1 and ((ord(a[count+1])-ord('A') in connection[current]) or (ord(a[count+1])-ord('A')+5 in connection[current])) :
        count+=1
        if (ord(a[count])-ord('A') in connection[current]):
            current=ord(a[count])-ord('A')
        else:
            current=ord(a[count])-ord('A')+5
        ans+=str(current)
    if count==len(a)-1:
        print ans
        continue
    print -1