	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(105).
-----Examples-----
Input:
2
AAB
AABE
Output:
501
-1
G = {0:[1,4,5],1:[0,2,6],2:[1,3,7],3:[2,4,8],4:[3,0,9],5:[0,7,8],6:[1,8,9],7:[2,5,9],8:[3,5,6],9:[4,6,7]}
L = {0:'A',1:'B',2:'C',3:'D',4:'E',5:'A',6:'B',7:'C',8:'D',9:'E'}

def Check(S):
    result = ''
    possibleStart = [k for k in list(L.keys()) if L[k] == S[0]]
    isBreak = False
    for c in S:
        found = False
        if result=='':
            result = result+str(possibleStart[0])
            last = possibleStart[0]
            found = True
        else:
            for k in G[last]:
                if L[k] == c:
                    result = result+str(k)
                    last = k
                    found = True
        if not found:
            isBreak = True
            break
        #print result
    if not isBreak:
        return result
    result = ''
    #print 'nextstart'
    for c in S:
        found = False
        if result=='':
            result = result+str(possibleStart[1])
            last = possibleStart[1]
            found = True
        else:
            for k in G[last]:
                if L[k] == c:
                    result = result+str(k)
                    last = k
                    found = True
        if not found:
            return str(-1)
        #print result
    return result       


T = int(input())
while T > 0:
    T = T - 1
    S = input()
    R = Check(S)
    print(R)

G = {0:[1,4,5],1:[0,2,6],2:[1,3,7],3:[2,4,8],4:[3,0,9],5:[0,7,8],6:[1,8,9],7:[2,5,9],8:[3,5,6],9:[4,6,7]}
L = {0:'A',1:'B',2:'C',3:'D',4:'E',5:'A',6:'B',7:'C',8:'D',9:'E'}

def Check(S):
    result = ''
    possibleStart = [k for k in list(L.keys()) if L[k] == S[0]]
    isBreak = False
    for c in S:
        found = False
        if result=='':
            result = result+str(possibleStart[0])
            last = possibleStart[0]
            found = True
        else:
            for k in G[last]:
                if L[k] == c:
                    result = result+str(k)
                    last = k
                    found = True
        if not found:
            isBreak = True
            break
        #print result
    if not isBreak:
        return result
    result = ''
    #print 'nextstart'
    for c in S:
        found = False
        if result=='':
            result = result+str(possibleStart[1])
            last = possibleStart[1]
            found = True
        else:
            for k in G[last]:
                if L[k] == c:
                    result = result+str(k)
                    last = k
                    found = True
        if not found:
            return str(-1)
        #print result
    return result       


T = int(input())
while T > 0:
    T = T - 1
    S = input()
    R = Check(S)
    print(R)
