题目描述

Banana Rocks Inc 正在研发一项革命性技术，用于执行常见的编辑操作“替换所有字符”。他们的实现会将给定文本中某个字符的所有出现替换为另一个字符。（如果该字符未出现在文本中，则操作会执行但无实际效果。）

例如，如果初始文本为 CODEJAMWORLDFINALS，执行将 A 替换为 o 的操作后，新文本为 CODEJOMWORLDFINOLS。若在该结果上再执行将 o 替换为 y 的操作，最终文本为 CYDEJYMWYRLDFINYLS。

遗憾的是，该实现尚未完成，因此只能执行特定列表中的 $\mathbf{N}$ 对字符的替换。此外，即使实现了将某个字符 $c_1$ 替换为另一个字符 $c_2$ 的操作，反向将 $c_2$ 替换为 $c_1$ 的操作可能实现也可能未实现。

你需要尝试所有已实现的替换操作。给定一个初始字符串 $\mathbf{S}$ 作为初始文本，你可以按任意顺序执行任意次数的替换操作：第一次替换作用于 $\mathbf{S}$，第 $(i+1)$ 次替换作用于第 $i$ 次替换后的结果。唯一的要求是在此过程中每个已实现的替换操作至少执行一次。每个替换操作的执行次数无上限。

允许的字符包括十进制数字、大小写英文字母。在此问题中，同一字母的大小写被视为不同字符。

在执行完最后一次替换操作后，最终文本中可能出现的最大唯一字符数是多少？

输入格式

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例包含两行：第一行是一个字符串 $\mathbf{S}$ 和一个整数 $\mathbf{N}$，分别表示初始文本和已实现的替换操作数量。第二行包含 $\mathbf{N}$ 个两字符的字符串 $\mathbf{R}_1, \mathbf{R}_2, \ldots, \mathbf{R}_\mathbf{N}$，表示已实现的替换操作。$\mathbf{A}_i$ 和 $\mathbf{B}_i$ 分别是 $\mathbf{R}_i$ 的第一个和第二个字符。第 $i$ 个替换操作表示将所有 $\mathbf{A}_i$ 替换为 $\mathbf{B}_i$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在以某种顺序对 $\mathbf{S}$ 执行所有已实现替换操作（每个至少一次）后，最终文本中可能出现的最大唯一字符数。

输入输出样例 #1

输入 #1

4
CODEJAMWORLDFINALS 2
AO OY
xyz 3
xy zx yz
CJ 4
20 2O HC KS
AB 2
Ab bA

输出 #1

Case #1: 14
Case #2: 2
Case #3: 2
Case #4: 2

输入输出样例 #2

输入 #2

1
1234 5
12 2X X3 31 X2

输出 #2

Case #1: 4

说明/提示

样例解释

样例测试集 1 符合测试集 1 的限制。另一个不符合这些限制的样例可能出现在测试集 2 中。

样例 #1 对应题目描述中的例子。注意，若按描述中的顺序执行替换操作，最终文本中有 13 个不同字符；但若以相反顺序各执行一次，则可得到 CYDEJOMWYRLDFINOLS，其中包含 14 个不同字符。

在样例 #2 中，按从左到右的顺序各执行一次替换操作，最终文本中可得到 2 个不同字符。

在样例 #3 中，所有替换操作均不影响文本，因此执行顺序无关紧要。最终文本始终为原始的两个字母。注意，替换操作可能包含初始文本中未出现的字符，且初始文本也可能包含替换操作中未出现的字符。

在样例 #4 中，请记住大写 $\mathbf{B}$ 与小写 $\mathbf{b}$ 是不同的字符。

在此附加样例中，一种可能的替换顺序为 X3 2X X2 2X 12 31。该过程从 $\mathbf{S}$ 开始依次生成以下字符串：1234 1234 1X34 1234 1X34 2X34 2X14。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• 对于所有 $i$，$2 \leq \text{初始文本 } \mathbf{S} \text{ 的长度} \leq 1000$。
• $\mathbf{S}$ 的每个字符为大写或小写英文字母或十进制数字。
• 对于所有 $i$，$\mathbf{A}_i$ 为大写或小写英文字母或十进制数字。
• 对于所有 $i$，$\mathbf{B}_i$ 为大写或小写英文字母或十进制数字。
• 对于所有 $i$，$\mathbf{A}_i \neq \mathbf{B}_i$。
• 对于所有 $i \neq j$，$(\mathbf{A}_i, \mathbf{B}_i) \neq (\mathbf{A}_j, \mathbf{B}_j)$（每个替换操作唯一）。

测试集 1（15 分，可见判定）

• $2 \leq \mathbf{N} \leq 62$。
• 对于所有 $i \neq j$，$\mathbf{B}_i \neq \mathbf{B}_j$。

测试集 2（27 分，隐藏判定）

• $2 \leq \mathbf{N} \leq 62 \times 61$。