Banana Rocks Inc 即将推出一项革命性的技术，用于执行常见的编辑操作“全部替换”。他们的实现会将给定文本中出现的每一个字符替换为另一个字符。（如果该字符未在文本中出现，则操作会执行但不会产生任何效果。）

例如，如果初始文本为 CODEJAMWORLDFINALS，执行将 A 替换为 O 的操作，新文本将变为 CODEJOMWORLDFINOLS。如果在此结果上执行另一个将 O 替换为 Y 的操作，最终文本将变为 CYDEJYMWYRLDFINYLS。

遗憾的是，该实现尚不完整，因此它只能执行来自 $N$ 个字符对列表中的替换。此外，即使实现了将特定字符 $c_1$ 替换为另一个字符 $c_2$ 的操作，将 $c_2$ 反向替换为 $c_1$ 的操作也可能并未实现。

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

允许使用的字符为十进制数字以及大小写英文字母。在本题中，同一字母的大小写形式被视为不同的字符。

请问在执行最后一次替换后，结果文本中可能出现的最大唯一字符数量是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行。第一行包含一个字符串 $S$ 和一个整数 $N$：初始文本以及已实现替换的数量。第二行包含 $N$ 个双字符字符串 $R_1, R_2, \dots, R_N$，表示已实现的替换。$A_i$ 和 $B_i$ 分别是 $R_i$ 的第一个和第二个字符。第 $i$ 个已实现的替换对应于将所有出现的 $A_i$ 替换为 $B_i$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在将所有已实现的替换各执行一次或多次（以某种顺序）后，结果文本中可能出现的最大唯一字符数量。

数据范围

$1 \le T \le 100$。 $2 \le \text{length of } S \le 1000$。 $S$ 中的每个字符均为大写或小写英文字母或十进制数字。 $A_i$ 为大写或小写英文字母或十进制数字。 $B_i$ 为大写或小写英文字母或十进制数字。 $A_i \neq B_i$。 $(A_i, B_i) \neq (A_j, B_j)$，对于所有 $i \neq j$（每个替换都是唯一的）。

子任务 1

$2 \le N \le 62$。 $B_i \neq B_j$，对于所有 $i \neq j$。

子任务 2

$2 \le N \le 62 \times 61$。

样例

样例输入 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

说明

上述样例满足子任务 1 的限制。以下是一个不满足该限制的额外样例：

1
1234 5
12 2X X3 31 X2

该样例的正确输出为 Case #1: 4。

在这个额外样例中，一种可能性是按以下顺序执行替换：X3 2X X2 2X 12 31。此过程从 $S$ 开始，经过以下字符串：1234 1234 1X34 1234 1X34 2X34 2X14。