Description

在 Unix 计算机中，数据存储在目录中。存在一个根目录，根目录下可以包含若干名称不同的目录。这些目录下还可以包含更多的目录，依此类推。

一个目录可以通过其名称和父目录（即直接包含它的目录）唯一确定。这通常通过路径来编码，路径由若干部分组成，每一部分前面都有一个正斜杠（'/'）。最后一部分是该目录的名称，其余部分描述其父目录的路径。例如，考虑如下路径：

/home/gcj/finals

该路径指的是名为 "finals" 的目录，它位于 "/home/gcj" 所描述的目录下，而 "/home/gcj" 又指的是名为 "gcj" 的目录，位于 "/home" 所描述的目录下。在这个路径中，只有一部分，意味着它指的是根目录下名为 "home" 的目录。

要创建一个目录，可以使用 mkdir 命令。你需要指定一个路径，mkdir 会创建该路径描述的目录，但前提是其父目录已经存在。例如，如果你想从零开始创建 "/home/gcj/finals" 和 "/home/gcj/quals" 这两个目录，你需要四条命令：

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

给定你计算机上已经存在的所有目录，以及你想要新建（如果尚未存在）的目录集合，你需要用多少条 mkdir 命令？

Input Format

输入的第一行包含测试用例数 $T$。接下来有 $T$ 组测试用例。每组用例的第一行包含两个整数 $N$ 和 $M$，用空格分隔。

接下来的 $N$ 行，每行给出你计算机上已经存在的一个目录的路径。该列表将包含你计算机上除根目录以外的所有已存在目录（根目录在每台计算机上都存在，因此无需显式列出）。

接下来的 $M$ 行，每行给出你想要创建的一个目录的路径。

输入中的每个路径格式如题目描述所述。具体来说，路径由一个或多个小写字母或数字组成的字符串（即仅包含 'a'-'z' 和 '0'-'9'），每个字符串前都有一个正斜杠。这些字符串不会为空。

Output Format

对于每组测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你需要使用的 mkdir 命令数量。

3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b

Case #1: 4
Case #2: 0
Case #3: 4

Hint

限制条件

• $1 \leqslant T \leqslant 100$。
• 任意路径长度不超过 100 个字符。
• 已存在目录列表和待创建目录列表中不会有重复路径，但同一个路径可能在两者中各出现一次（见下方示例 case #2）。
• 如果某个目录已在你计算机上存在，则其父目录也必然在列表中，除非父目录是根目录。
• 输入文件总长度不超过 100,000 字节。

小数据范围（12 分，测试集 1 - 可见）

• $0 \leqslant N \leqslant 10$。
• $1 \leqslant M \leqslant 10$。

大数据范围（14 分，测试集 2 - 隐藏）

• $0 \leqslant N \leqslant 100$。
• $1 \leqslant M \leqslant 100$。

由 ChatGPT 4.1 翻译