34399번 - Spelling with Chemistry 다국어

문제

Each element on the periodic table has a one or two letter symbol. These symbols can be combined to spell words, and many times there are multiple ways of spelling a word using different combinations of symbols. Can you determine how many different ways a word can be spelled using the symbols?

For example, the word "bacon" can be spelled 3ドル$ different ways:

1. Barium, Cobalt, Nitrogen: BaCoN
2. Boron, Actinium, Oxygen, Nitrogen: BAcON
3. Barium, Carbon, Oxygen, Nitrogen: BaCON

However, your friend from another universe wants to spell words with the elements found there, which are different than the elements in our universe. So, your input will include the set of symbols in the periodic table for that particular universe. In this other universe, they don't follow the same naming convention that we do, so the provided symbols could be up to 5ドル$ letters in length.

입력

The first line of input will contain an integer $N$ (1ドル \leq N \leq 200$), the number of symbols in that universe.

The next $N$ lines will contain a single unique symbol, each between 1ドル$ and 5ドル$ letters in length.

The next line of input will contain an integer $M$ (1ドル \leq M \leq 20$), the number of words for which you should determine how many ways they can be spelled.

The next $M$ lines each contain a single word, each between 1ドル$ and 40ドル$ letters in length, containing only lowercase letters.

출력

Output a total of $M$ lines, each line indicating the number of ways that the corresponding input word can be spelled using the symbols in the periodic table for that universe. If a word is impossible to spell, output a 0ドル$ on that line.

제한

노트