Description

Shushu noticed that many computer terms are abbreviations. For example, GDB is the abbreviation of Gnu DeBug. However, sometimes an abbreviation may have multiple possible full forms. For example, LINUX can be understood as:

1. LINus’s UniX
2. LINUs’s miniX
3. Linux Is Not UniX

Now Shushu gives an abbreviation and a fixed full form (several words separated by spaces). Some words in the full form may be invalid and should be ignored. A valid abbreviation requires that:

• Each valid word contributes at least one character that appears in the abbreviation.
• The selected letters must appear in order in the full form (within each word and across words).

For the given abbreviation and full form, how many interpretations are there? An interpretation is defined by the positions of the letters chosen in each valid word. If any letter’s position differs, they are considered different interpretations.

Input Format

The first line contains an integer $N$, the number of invalid words.

The next $N$ lines each contain one invalid word, consisting of lowercase letters.

Then follow multiple queries. Each query provides an abbreviation (uppercase letters only) followed by a full form. Input ends with a line containing LASTCASE.

Output Format

For each query, first output the abbreviation. If the abbreviation is not valid, output is not a valid abbreviation; otherwise, output can be formed in i ways (where $i$ is the number of interpretations).

2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE

ACM can be formed in 2 ways
RADAR is not a valid abbreviation

Hint

Constraints

For all testdata, $1 \le N \le 100$, the length of each string does not exceed $150$, the number of queries does not exceed $20$, and the number of interpretations does not exceed $10^9$.

Translated by ChatGPT 5