Shortening codes

A binary coding of a text, consisting of letters of the english alphabet, can be done in the following way. Every character is associated to an integer, beginning with "A"=0 to "Z"=25 in alphabetical order and continuing with "a"=26 to "z"=51, which has to be represented in binary form and - if necessary - filled up with leading zeros, if less than 6 bits were needed otherwise. Your task is to (de)code a line of readable text or binary code respectively.

Input

Input starts with a positive integer t (t<100) in a single line. Then follow t lines, every line containing either a readable text (with less than 80 characters) or a binary coded string (with less than 500 digits). A readable text will only consist of letters of the english alphabet and single whitespaces to separate words, which shouldn't be converted to binary code. A binary coded string will only consist of ones and zeros as well as single whitespaces to separate coded words.

Output

For every testcase (de)code the respective line either to binary code or to readable text and print the result.

Example

Input:
2
010010011110011110 011000101000101110
Make it short

Output:
See You
001100011010100100011110 100010101101 101100100001101000101011101101