English Reading

You may have seen a sentence like this on the internet.

It is itnersetnig taht pepole can raed smoe grabeld wrods.

The original sentence is 'It is interesting that people can read some garbled words'. In each word, every letter except the first and last letters has been rearranged. Suppose that someone who knows an English word can still read it whenever the first letter, the last letter, and the multiset of letters between them are the same, regardless of the order of the middle letters.

Because of this, one word may be interpreted as several dictionary words. For instance, abcde may be interpreted as abcde, abdce, acbde, acdbe, adbce, or adcbe, since they have the same first and last letters and the same middle letters. Only words that actually appear in the dictionary are valid interpretations.

Given English sentences, compute the number of ways to interpret each sentence by replacing each word with a valid dictionary word. A sentence contains one or more words, separated by a single space.

The first line contains the number of dictionary words N (0 <= N <= 10,000). Each of the next N lines contains one English dictionary word. Each word has length at most 100.

The next line contains the number of sentences M (0 <= M <= 10,000). Each of the next M lines contains one English sentence to interpret. Each sentence has length at most 10,000.

English words consist only of uppercase and lowercase English letters. Uppercase and lowercase letters are considered different.

For each sentence, print the number of possible interpretations on its own line. You may assume that every answer fits in a 32-bit signed integer.