Decoding Morse Sequences

Before the digital age, the most common "binary" code for radio communication was Morse code. In Morse code, each symbol is encoded as a sequence of short and long pulses (called dots and dashes). The table below gives the Morse code for the alphabet, where dots and dashes are written as the ASCII characters "." and "-":

If there are no pauses between letters, a single Morse sequence may have several interpretations. For example, the sequence -.-..-- can be decoded as CAT or as NXT (among others). A human operator would use additional context, such as a dictionary of the language, to pick the right decoding; but even with such a dictionary, one Morse sequence may yield several phrases.

Write a program that, for each data set:

• reads a Morse sequence and a list of words (a dictionary);
• computes the number of distinct phrases that can be formed from the given Morse sequence using words from the dictionary;
• writes the result.

A phrase is an ordered sequence of dictionary words (a word may be used several times); two phrases are different when their sequences of words differ. We count only full matches: the entire Morse sequence must be covered by the words with nothing left over.

The first line of the input contains one positive integer d, the number of data sets (1 ≤ d ≤ 20). The data sets follow.

The first line of each data set contains a Morse sequence: a nonempty string of at most 10,000 characters "." and "-" with no spaces.

The second line contains one integer n, the number of words in the dictionary (1 ≤ n ≤ 10,000). Each of the next n lines contains one dictionary word: a nonempty string of at most 20 capital letters from "A" to "Z". No word appears in the dictionary more than once.

The output consists of exactly d lines, one per data set. Line i contains a single integer: the number of distinct phrases into which the Morse sequence of the i-th data set can be parsed. You may assume this number is at most 2·10^9 for each data set.