For given text, encipher it with Polybius square and print.

Input

The first line of the standard input contains one integer t (t<10001) which is the number of test cases.

In each of the next t lines there is a string n (could contain spaces, which you dont have to encipher; apart from spaces it will be only made of big letters - 'A' to 'Z').

Output

For each test, print ciphered string n.

Score

Score is source length.

Example

Input:
4
SHORTENING IS FUNNY
NO IT ISNT
TRY IT AND ASCERTAIN
JI JI
Output:
43 23 34 42 44 15 33 24 33 22 24 43 21 45 33 33 54
33 34 24 44 24 43 33 44
44 42 54 24 44 11 33 14 11 43 13 15 42 44 11 24 33
24 24 24 24