描述

设计 ACM 编程竞赛题目的出题者经常喜欢在题面中加入缩写 “ACM”。过去的世界总决赛题目中就有 “公寓建设管理”（Apartment Construction Management），“文化与影视学会”（Atheneum of Culture and Movies），“封面制造商协会”（Association of Cover Manufacturers），“ACM 航空公司”（ACM Airlines），“计算海洋生物学会”（Association for Computational Marinelife），甚至还有一种昆虫 “阿米莉亚奶酪螨”（Amelia Cheese Mite）。然而，以 A、C、M 开头且语义通顺的词组组合是有限的，出题者们已渐渐枯竭（想出 “反定建立论地下语意金属语言学” 这种题目组合实在太难）。幸好，现代文化提供了更多设计自由，比如：

GDB — Gnu DeBugger LINUX — “LINus’s UniX” 或 “LINUs’s miniX” 或 “Linux Is Not UniX” SNOBOL — StriNg Oriented symBOlic Language SPITBOL — SPeedy ImplemenTation of snoBOL

这些例子遵循的规则似乎是：

1. 忽略不重要的词（如 “of”、“a”、“the” 等）。
2. 缩写字母必须按顺序出现在词组中所有重要词的字母序列中。
3. 每个重要词至少贡献缩写中的一个字母（同一字母的多次出现视为不同位置）。

实际生活中这些规则常被打破。例如 RADAR 缩写自 “RAdio Detecting And Ranging”，如果 “and” 视为不重要词，则根据上述规则 RADAR 并不合法（但 RADR、RADRAN 或 DODGING 都是合法的）。现在你需要根据给定的不重要词表和多组测试，计算每个缩写可按上述规则从对应词组中组成的不同方式数。

输入

输入文件包含多个场景。每个场景首先给出一个整数 $n$（$1 \le n \le 100$），随后 $n$ 行，每行一个小写不重要词（无额外空白）。若 $n=0$ 则输入结束。随后是一系列测试用例，每行一个测试，用例以一行 “LAST CASE” 结束。每个测试用例行首是一个缩写（仅大写字母），后面是一个短语（仅小写字母和空格）。保证缩写长度至少 1，短语中至少有一个重要词。任意输入行（包括缩写、短语及空格）不超过 150 个字符。

输出

对于每个测试用例，输出：

<缩写> is not a valid abbreviation

或

<缩写> can be formed in i ways

其中 $i$ 是按规则组成缩写的不同方案数，且不超过 32 位有符号整型范围。

输入数据 1

2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE
2
a
an
APPLY an apple a day
LAST CASE
0

输出数据 1

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

来源

East Central North America 2005