Description

有一个都市传说：如果你在 Google 首页搜索“Google”，宇宙就会崩溃。我们有个秘密要告诉你……这是真的！请不要尝试，也不要告诉别人。好吧，其实不是，我们只是开玩笑。

但在遥远的另一个宇宙中，情况却并非如此。在那个宇宙里，如果你在任何搜索引擎上搜索该搜索引擎的名字，宇宙真的会崩溃！

为了解决这个问题，人们想出了一个有趣的办法。所有的查询会被集中到一起，然后交给一个中央系统来决定每个查询由哪个搜索引擎处理。中央系统会将一系列查询发送给某个搜索引擎，并且可以随时切换到另一个搜索引擎。所有查询必须按照收到的顺序处理。中央系统绝不能将一个查询发送给名字与该查询相同的搜索引擎。为了降低成本，切换搜索引擎的次数应尽量少。

你的任务是：假设我们以最优方式编程，请你告诉我们中央系统需要切换多少次搜索引擎。

Input Format

输入文件的第一行包含测试用例数 $N$。接下来有 $N$ 组测试数据。

每组测试数据首先包含一个整数 $S$，表示搜索引擎的数量。接下来的 $S$ 行，每行包含一个搜索引擎的名字。每个搜索引擎名字不超过一百个字符，只包含大写字母、小写字母、空格和数字。不会有两个搜索引擎名字相同。

接下来一行包含一个整数 $Q$，表示收到的查询数量。接下来的 $Q$ 行，每行包含一个查询。每个查询都是本组测试数据中某个搜索引擎的名字。

Output Format

对于每组输入数据，输出：

Case #$X$: $Y$

其中 $X$ 是测试用例编号，$Y$ 是切换搜索引擎的次数。初始选择搜索引擎不计为一次切换。

2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

Case #1: 1
Case #2: 0

Hint

样例解释

在第一个测试用例中，一种可行的方案是先使用 Dont Ask，在第 8 个查询后切换到 NSM。

在第二个测试用例中，你可以一直使用 B9，无需切换。

数据范围

• $0 < N \leq 20$

小数据集（5 分，测试点 1 - 可见）

• $2 \leq S \leq 10$
• $0 \leq Q \leq 100$

大数据集（20 分，测试点 2 - 隐藏）

• $2 \leq S \leq 100$
• $0 \leq Q \leq 1000$

由 ChatGPT 4.1 翻译