Abbreviations

Acronyms are often formed more flexibly than just taking the first letter of each word. For example, GDB stands for Gnu DeBugger: the letters are taken from the words in order, and a single word (DeBugger) may contribute several letters.

We form abbreviations by the following rules:

1. Meaningless words (such as of, a, the) are ignored.
2. The letters taken from each word must appear in that word's left-to-right order.
3. Every meaningful word must be used — each contributes at least one letter.

Concretely, after deleting the meaningless words, let the remaining meaningful words, in their original order, be $w_1, w_2, \dots, w_k$. The abbreviation must be split into $k$ consecutive non-empty pieces $p_1 p_2 \dots p_k$ whose concatenation is the whole abbreviation, where each piece $p_i$ is a subsequence of word $w_i$. Letters are matched case-insensitively (the abbreviation is uppercase, the words are lowercase).

Not every real abbreviation obeys these rules. For instance, RADAR stands for "RAdio Detecting And Ranging"; because it draws a letter from the ignored word "and", it cannot be formed under these rules.

Given the list of meaningless words, an abbreviation, and a sentence, count the number of different ways the abbreviation can be formed. Two ways are different if the abbreviation is split between the words differently, or if any letter is taken from a different position within its word.

The input consists of several test cases. The first line of each test case contains an integer $n$ ($1 \le n \le 100$), the number of meaningless words. Each of the next $n$ lines contains one meaningless word in lowercase.

After that come one or more query lines. Each query line contains an uppercase abbreviation followed by a lowercase sentence (lowercase words separated by spaces). The abbreviation has length at least 1, and the sentence contains at least one meaningless word. Every abbreviation and every sentence is at most 150 characters long. The list of queries ends with a line containing exactly LAST CASE.

The input ends with a test case whose first line is 0.

For each query, if the abbreviation cannot be formed, print

<abbreviation> is not a valid abbreviation

otherwise print

<abbreviation> can be formed in i ways

where i is the number of ways to form it. The value i fits in a 32-bit signed integer.