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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "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]}\nL = {0:'A',1:'B',2:'C',3:'D',4:'E',5:'A',6:'B',7:'C',8:'D',9:'E'}\n\ndef Check(S):\n    result = ''\n    possibleStart = [k for k in list(L.keys()) if L[k] == S[0]]\n    isBreak = False\n    for c in S:\n        found = False\n        if result=='':\n            result = result+str(possibleStart[0])\n            last = possibleStart[0]\n            found = True\n        else:\n            for k in G[last]:\n                if L[k] == c:\n                    result = result+str(k)\n                    last = k\n                    found = True\n        if not found:\n            isBreak = True\n            break\n        #print result\n    if not isBreak:\n        return result\n    result = ''\n    #print 'nextstart'\n    for c in S:\n        found = False\n        if result=='':\n            result = result+str(possibleStart[1])\n            last = possibleStart[1]\n            found = True\n        else:\n            for k in G[last]:\n                if L[k] == c:\n                    result = result+str(k)\n                    last = k\n                    found = True\n        if not found:\n            return str(-1)\n        #print result\n    return result       \n\n\nT = int(input())\nwhile T > 0:\n    T = T - 1\n    S = input()\n    R = Check(S)\n    print(R)\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14737