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 = "let_to_num = {'A':[0,5], 'B':[1,6], 'C':[2,7], 'D':[3,8], 'E':[4,9]}\n\nnum_to_let = {0:'A', 1:'B', 2:'C', 3:'D', 4:'E',\n              5:'A', 6:'B', 7:'C', 8:'D', 9:'E'}\n\nconnections = {0:(1,4,5), 1:(0,2,6), 2:(1,3,7), 3:(2,4,8), 4:(0,3,9), 5:(0,7,8),\n               6:(1,8,9), 7:(2,5,9), 8:(3,5,6), 9:(4,6,7)}\n\nT = int(input())\n\nfor i in range(T):\n    s = input()\n    out_1, out_2= [],[]\n    flag1, flag2 = True, True\n    for c in range(len(s)):\n        #print out_1, out_2, flag1, flag2\n        if c == 0:\n            out_1.append(let_to_num[s[c]][0])\n            out_2.append(let_to_num[s[c]][1])\n            #print out_1, out_2, '\\n'\n        else:\n            if flag1:\n                conn_1 = set(connections[out_1[-1]])\n                to_conn_1 = set(let_to_num[s[c]])\n                \n                if len(conn_1.intersection(to_conn_1))==0:\n                    flag1 = False\n                else:\n                    out_1.extend(list(conn_1.intersection(to_conn_1)))\n                    \n                #print 'out1',conn_1, to_conn_1, flag1, conn_1.intersection(to_conn_1)\n            if flag2:\n                conn_2 = set(connections[out_2[-1]])\n                to_conn_2 = set(let_to_num[s[c]])\n                \n                if len(conn_2.intersection(to_conn_2))==0:\n                    flag2 = False\n                else:\n                    out_2.extend(list(conn_2.intersection(to_conn_2)))\n                #print 'out2', conn_2, to_conn_2, flag2, conn_2.intersection(to_conn_2)\n            #print out_1, out_2, flag1, flag2, '\\n'\n            if (not flag1) and (not flag2):\n                break\n    if (not flag1) and (not flag2):\n        print(-1)\n        continue\n    elif flag1 and (not flag2):\n        print(''.join(str(k) for k in out_1))\n        continue\n    elif flag2 and (not flag1):\n        print(''.join(str(k) for k in out_2))\n        continue\n    else:\n        print(min(''.join(str(k) for k in out_1), ''.join(str(k) for k in out_2)))\n        continue\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15353