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

Difficulty: interview

Starter code:

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

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

connections = {0:(1,4,5), 1:(0,2,6), 2:(1,3,7), 3:(2,4,8), 4:(0,3,9), 5:(0,7,8),
               6:(1,8,9), 7:(2,5,9), 8:(3,5,6), 9:(4,6,7)}

T = int(input())

for i in range(T):
    s = input()
    out_1, out_2= [],[]
    flag1, flag2 = True, True
    for c in range(len(s)):
        #print out_1, out_2, flag1, flag2
        if c == 0:
            out_1.append(let_to_num[s[c]][0])
            out_2.append(let_to_num[s[c]][1])
            #print out_1, out_2, '\n'
        else:
            if flag1:
                conn_1 = set(connections[out_1[-1]])
                to_conn_1 = set(let_to_num[s[c]])
                
                if len(conn_1.intersection(to_conn_1))==0:
                    flag1 = False
                else:
                    out_1.extend(list(conn_1.intersection(to_conn_1)))
                    
                #print 'out1',conn_1, to_conn_1, flag1, conn_1.intersection(to_conn_1)
            if flag2:
                conn_2 = set(connections[out_2[-1]])
                to_conn_2 = set(let_to_num[s[c]])
                
                if len(conn_2.intersection(to_conn_2))==0:
                    flag2 = False
                else:
                    out_2.extend(list(conn_2.intersection(to_conn_2)))
                #print 'out2', conn_2, to_conn_2, flag2, conn_2.intersection(to_conn_2)
            #print out_1, out_2, flag1, flag2, '\n'
            if (not flag1) and (not flag2):
                break
    if (not flag1) and (not flag2):
        print(-1)
        continue
    elif flag1 and (not flag2):
        print(''.join(str(k) for k in out_1))
        continue
    elif flag2 and (not flag1):
        print(''.join(str(k) for k in out_2))
        continue
    else:
        print(min(''.join(str(k) for k in out_1), ''.join(str(k) for k in out_2)))
        continue


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)


D = {0: [1, 4, 5], 1: [0, 2, 6], 2: [1, 3, 7],
     3: [2, 4, 8], 4: [0, 3, 9], 5: [0, 7, 8],
     6: [1, 8, 9], 7: [2, 5, 9], 8: [3, 5, 6], 9: [4, 6, 7]}

E = ['A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E']

for _ in range(eval(input())):
    S = input()
    solved = False
    for i in range(10):
        if not solved:
            if E[i] == S[0]:
                solved = True
                ans = str(i)
                for x in S[1:]:
                    for y in D[int(ans[-1])]:
                        if E[y] == x:
                            ans += str(y)
                            break
                    else:
                        solved = False
    if solved:
        print(ans)
    else:
        print(-1)