E. O: dah, dah, dah!

Time limit: 1s

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	- - - -.	&	.-...

Input

The first line of input gives the number of cases, $T$ ($1\; \le \; T\; \le \; 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.

Output

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.

Sample input

2
... --- ...
.--- --- -...  -.. --- -. .  ..--..  ..-. .. -. . -.-.--

Sample output

Message #1
SOS

Message #2
JOB DONE ? FINE!

---

#include <iostream>
#include <map>
#include <ctype.h>
using namespace std;

int main() {
    map<string, char> r;
    r[".-"] = 'A', r["-..."] = 'B', r["-.-."] = 'C';
    r["-.."] = 'D', r["."] = 'E', r["..-."] = 'F';
    r["--."] = 'G', r["...."] = 'H', r[".."] = 'I';
    r[".---"] = 'J', r["-.-"] = 'K', r[".-.."] = 'L';
    r["--"] = 'M', r["-."] = 'N', r["---"] = 'O';
    r[".--."] = 'P', r["--.-"] = 'Q', r[".-."] = 'R';
    r["..."] = 'S', r["-"] = 'T', r["..-"] = 'U';
    r["...-"] = 'V', r[".--"] = 'W', r["-..-"] = 'X';
    r["-.--"] = 'Y', r["--.."] = 'Z', r["-----"] = '0';
    r[".----"] = '1', r["..---"] = '2', r["...--"] = '3';
    r["....-"] = '4', r["....."] = '5', r["-...."] = '6';
    r["--..."] = '7', r["---.."] = '8', r["----."] = '9';
    r[".-.-.-"] = '.', r["--..--"] = ',', r["..--.."] = '?';
    r[".----."] = '\'', r["-.-.--"] = '!', r["-..-."] = '/';
    r["-.--."] = '(', r["-.--.-"] = ')', r[".-..."] = '&';
    r["---..."] = ':', r["-.-.-."] = ';', r["-...-"] = '=';
    r[".-.-."] = '+', r["-....-"] = '-', r["..--.-"] = '_';
    r[".-..-."] = '\"', r[".--.-."] = '@';
    int t, cases = 0;
    string in;
    cin >> t;
    cin.ignore(100, '\n');
    while(t--) {
        cases++;
        cout << "Message #" << cases << endl;
        getline(cin, in);
        int len = in.length(), cnt = 0;
        for(int i = 0; i < len; i++) {
            if(isspace(in[i])) {
                if(cnt == 1) {
                    cout << ' ';
                    cnt = 0;
                } else
                    cnt++;
                continue;
            }
            int j = i;
            string s = "";
            while(!isspace(in[j]) && j < len) {
                s += in[j];
                j++;
            }
            cout << r[s];
            cnt = 0;
            i = j-1;
        }
        cout << endl;
        if(t)
            cout << endl;

    }
    return 0;
}