描述

背景

你可能知道，人类的信息处理系统是一个出色的文本识别器，甚至能够处理像下面这样混乱的句子： “The ACM Itrenntaoial Clloegaite Porgarmmnig Cnotset (IPCC)” “porvdies clolgee stuetnds wtih ooppriuntetiis to itnrecat” “wtih sutednts form ohetr uinevsrtieis.”

问题

人们声称，一般来说，使用以下规则就能理解这些句子：每个单词的首字母和尾字母保持不变，中间的所有字符可以随意重新排列。

由于你是一名持怀疑态度的ACM程序员，你立即着手编写如下程序：

给定一个句子和一个单词字典，你能找出有多少个不同的句子可能映射到相同的编码形式？

输入

第一行包含测试用例的数量。每个测试用例以一行内容开始，该行包含字典中单词的数量$n$（$0 \leq n \leq 10000$），接下来的$n$行打印出这些单词。之后有一行包含需要用前面字典进行测试的句子数量$m$（$0 \leq m \leq 10000$），然后是$m$行包含这些句子的内容。句子仅由字母a - z、A - Z和空格组成，最大长度为$10000$个字符。假设字典中的每个单词长度限制为$100$个字符。

输出

每个测试用例的输出以一行 “Scenario #i:” 开始，其中$i$是从$1$开始的测试用例编号。对于每个句子，在单独的一行中输出可以组成的句子数量。可以保证这个数量能用有符号32位数据类型表示。每个测试用例的输出以一个空行结束。

输入数据1

2
3
ababa
aabba
abcaa
2
ababa
abbaa
14
bakers
brakes
breaks
binary
brainy
baggers
beggars
and
in
the
blowed
bowled
barn
bran
1
brainy bakers and beggars bowled in the barn

输出数据1

Scenario #1:
2
2

Scenario #2:
48

来源

2005年德国达姆施塔特工业大学编程竞赛