题目描述

Alan just had his first cryptography class in school today. He decided to apply what he learned and come up with his own cipher. He will map each English letter from A to Z to a decimal digit $0$ through $9$. He will then try to encode each word to a string consisting of decimal digits by replacing each letter in the word with its mapped digit.

In his excitement, Alan failed to notice that there are $26$ letters in the English alphabet and only $10$ decimal digits. As a result, there might be collisions, that is, pairs of different words whose encoding is the same.

Given a list of $N$ words that Alan wants to encode and the mapping that he uses, can you find out if there would be any collisions between words on the list?

输入格式

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case contains 26 decimal digits (integers between 0 and 9, inclusive) $D_A$, $D_B$, …, $D_Z$, representing the mapping that Alan uses. A letter $\alpha$ is mapped to digit $D_\alpha$.

The second line of each test case contains N, the number of words Alan will encode.

The $i$-th of the last N lines contains a string $S_i$, representing the $i$-th word Alan will encode.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is either YES, if there is at least one pair of different words from the list whose encoding coincides, and NO otherwise.

2
0 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4
ABC
BC
BCD
CDE
0 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3
CDE
DEF
EFG

Case #1: NO
Case #2: YES

提示

Sample Explanation

In Sample Case #1, the mapping for A is 0, for B is 1, for C is 2, for D is 3, and for E is 3. With this mapping, ABC is encoded as 012, BC is encoded as 12, BCD as 123, and CDE as 233. Since all of these encodings are distinct, there are no collisions.

In Sample Case #2, the mapping for C is 2, for D is 3, for E is 3, for F is 3, and for G is 3. With this mapping, CDE is encoded as 233, DEF as 333, and EFG as 333. Since the encoding for DEF and EFG is the same, there is a collision.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $0 \leq \mathbf{D}_{\alpha} \leq 9$, for all $\alpha$.
• $1 \leq$ the length of $\mathbf{S}_{i} \leq 10$, for all $i$.
• Each character of $\mathbf{S}_{i}$ is an uppercase English letter A through Z, for all $i$.
• $\mathbf{S}_{i} \neq \mathbf{S}_{j}$, for all $i \neq j$.

Test Set 1 (4Pts, Visible Verdict)

• $1 \leq \mathbf{N} \leq 100$.

Test Set 2 (10Pts, Visible Verdict)

• $1 \leq \mathbf{N} \leq 6 \times 10^{4}$.