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
import sys
t = int(sys.stdin.readline().rstrip())
while t != 0:
    s = sys.stdin.readline().rstrip()
    index = 1
    mode = False
    while index != len(s) and s[index] == s[0]:
        index += 1
    if index != len(s):
        mode = abs(ord(s[index])-ord(s[index-1])) in [2,3]
    x = str(ord(s[0])- (60 if mode else 65))
    answer = (x if index % 2 != 0 else '') + (str((int(x)+5)%10) + x)*(index/2)
    while index != len(s):
        v = abs(ord(s[index])-ord(s[index-1]))
        if (v in [1,4] and mode == True) or (v in [2,3] and mode == False):
            answer = "-1"
            break
        elif v == 0:
            mode = not mode
        answer += str(ord(s[index])-65+(5 if mode else 0))
        index += 1
    print answer
    t-=1