题目描述

Banana Rocks Inc is coming up with a revolutionary technology to perform the common edit operation "replace all". Their implementation replaces every occurrence of a character within a given text with another character. (If the character does not appear in the text, then the operation occurs but has no effect.)

For example, if the starting text is CODEJAMWORLDFINALS and an operation is performed to replace A with o, the new text would be CODEJOMWORLDFINOLS. If another operation is performed on that result to replace o with y, the final text would be CYDEJYMWYRLDFINYLS.

Unfortunately, the implementation is incomplete, so it can only perform replacements from a specific list of $\mathbf{N}$ pairs of characters. Also, even if a replacement of a specific character $c_1$ with another character $c_2$ is implemented, the reverse replacement of $c_2$ with $c_1$ may or may not be implemented.

You want to try all the implemented replacements. You are given some initial string $\mathbf{S}$ to use as the initial text. You can perform any number of replacements in sequential order: the first replacement is performed on $\mathbf{S}$, and the (i+1)-th replacement is performed on the result of performing the i-th replacement. The only requirement is that each implemented replacement is performed at least once during this process. There is no upper limit on how many times you may perform each replacement.

The allowed characters are decimal digits and uppercase and lowercase English alphabet letters. In this problem, uppercase and lowercase versions of the same letter are treated as distinct characters.

What is the maximum number of unique characters that can appear in a text that is the result of the last replacement performed?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of two lines. The first line contains a string $\mathbf{S}$ and an integer $\mathbf{N}$: the initial text and the number of implemented replacements. The second line contains $\mathbf{N}$ two-character strings $\mathbf{R}_1$, $\mathbf{R}_2$, ..., $\mathbf{R}_\mathbf{N}$, representing the implemented replacements. $\mathbf{A}_i$ and $\mathbf{B}_i$ are the first and second characters of $\mathbf{R}_i$, respectively. The i-th implemented replacement corresponds to replacing all occurrences of $\mathbf{A}_i$ with $\mathbf{B}_i$.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of unique characters that can appear in a text that is the result of performing all implemented replacements to $\mathbf{S}$ one or more times each, in some order.

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

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

1
1234 5
12 2X X3 31 X2

Case #1: 4

提示

Sample Explanation

Sample Test Set 1 meets the limits for Test Set 1. Another sample case that does not meet those limits could appear in Test Set 2.

Sample Case #1 is the one in the statement. Notice that if we perform the replacements in the order mentioned in the statement, we get 13 different characters in the final text. If we perform them both once in the other order, however, we can get CYDEJOMWYRLDFINOLS, which has 14 different characters.

In Sample Case #2, one way to get 2 different characters in the final text is to perform the replacements in the order given from left to right, once each.

In Sample Case #3, none of the replacements affect the text at all, so it does not matter how we apply them. We will always be left with the original two letters. Notice that replacements can contain characters not appearing in the initial text, and the initial text can contain characters not appearing in the implemented replacements.

In Sample Case #4, remember that uppercase $\mathbf{B}$ is not the same character as lowercase $\mathbf{b}$.

In this additional sample case, one possibility is to perform the replacements in the following order: X3 2X X2 2X 12 31. This process goes through the following strings, starting with S: 1234 1234 1X34 1234 1X34 2X34 2X14.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $2 \leq \text{length of } \mathbf{S} \leq 1000$, for all i.
• Each character of $\mathbf{S}$ is an uppercase or lowercase English alphabet letter or a decimal digit.
• $\mathbf{A}_i$ is an uppercase or lowercase English alphabet letter or a decimal digit, for all i.
• $\mathbf{B}_i$ is an uppercase or lowercase English alphabet letter or a decimal digit, for all i.
• $\mathbf{A}_i \neq \mathbf{B}_i$, for all i.
• $(\mathbf{A}_i, \mathbf{B}_i) \neq (\mathbf{A}_j, \mathbf{B}_j)$, for all $i \neq j$. (Each replacement is unique.)

Test Set 1 (15 Pts, Visible Verdict)

• $2 \leq \mathbf{N} \leq 62$.
• $\mathbf{B}_i \neq \mathbf{B}_j$, for all $i \neq j$.

Test Set 2 (27 Pts, Hidden Verdict)

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