Morse code is a method of transmitting textual information as a series of on-off tones, lights, or clicks that can be directly understood by a skilled listener or observer without special equipment. The International Morse Code encodes the ISO basic Latin alphabet, some extra Latin letters, the Arabic numerals and a small set of punctuation and procedural signals as standardized sequences of short and long signals called "dots" and "dashes" respectively, or "dis" and "dahs". Because many non-English natural languages use more than the 26 Roman letters, extensions to the Morse alphabet exist for those languages.

 

    Each character is represented by a unique sequence of dots and dashes. For example, the sequence of character 'A' is '.-', and the sequence of 'B' is '-...'. We get the sequences of all the upper case alphabets and make a Morse Code Table, just like the picture below.

 

 

    It's obviously that we should add some blanks between characters to avoid ambiguity, otherwise a Morse Code text can be interpreted as several meanings. Imagine that you get a Morse Code text '-.' and you don't know whether there exist blanks, you may interpret the text as 'N' or 'TE'.

 

    Now I give you the Morse Code Table(picture below) and a long text represented by Morse Code. Can you tell me how many proper interpretations you'll get by adding some blanks in the text?

    The first line of input file contains the total cases in the file.

    Each case just contain one string of dots ('.') and dashes ('-'). The length of the string won't be larger than 100,000.