Petersen Graph

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
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 W_{1}, W_{2}, ..., W_{L}, such that W_{i} is connected with W_{i + 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
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/PETERSEN 
Tags  bfs, cook52, graphs, kostya_by, simple, traversal 
Date Added:  25102014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 