Morse code is a method for long-distance transmission of textual information without using the usual symbols. Instead information is represented with a simpler, binary, alphabet composed of short and long beeps. The short beep is called dih, and the long beep is called dah. For instance, the code for the letter O is dah dah dah (three long beeps). Actually, because the codification is not prefix-free, there is also a third symbol, which is silence. The code between two letters is a simple silence, the code between two words is a double silence.
You have been assigned the job to translate a message in Morse code. The signal has already been digitalized in the following fashion: dih is represented by a dot (.), dah is represented by a dash (-). Simple and double silences are represented by a single space character and two space characters respectively.
The following table represents the Morse code of all the characters that your program need to be able to handle.
| Symbol | Code | Symbol | Code | Symbol | Code | Symbol | Code | Symbol | Code | Symbol | Code |
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | .- | J | .- - - | S | ... | 1 | .- - - - | . | .-.-.- | : | - - -... |
| B | -... | K | -.- | T | - | 2 | ..- - - | , | - -..- - | ; | -.-.-. |
| C | -.-. | L | .-.. | U | ..- | 3 | ...- - | ? | ..- -.. | = | -...- |
| D | -.. | M | - - | V | ...- | 4 | ....- | ' | .- - - -. | + | .-.-. |
| E | . | N | -. | W | .- - | 5 | ..... | ! | -.-.- - | - | -....- |
| F | ..-. | O | - - - | X | -..- | 6 | -.... | / | -..-. | _ | ..- -.- |
| G | - -. | P | .- -. | Y | -.- - | 7 | - -... | ( | -.- -. | " | .-..-. |
| H | .... | Q | - -.- | Z | - -.. | 8 | - - -.. | ) | -.- -.- | @ | .- -.-. |
| I | .. | R | .-. | 0 | - - - - - | 9 | - - - -. | & | .-... |
The first line of input gives the number of cases, T (1 ≤ T ≤ 10). T test cases follow. Each one is a sequence of dot, dash and space characters. Two messages are separated by a newline. The maximum length of a message is 2000.
The output is comprised of one paragraph for each message. The paragraph corresponding to the n-th message starts with the header Message #n, on a line on its own. Each decoded sentence of the message appears then successively on a line of its own. Two paragraphs are separated by a blank line. The sentences shall be printed in uppercase.