Migrated from Lutece 11 Judgment Day

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Today is the judgment day. The world is ending and all man will pay for their guilt and sin. Now the Almighty God has a long string, and some people’s name. He will take some letters from the string and use them to spell out those people’s name. What is the maximum number of the names that can be spelled, with each name be spelled at most once?

Input

The first line of input contains a number $T$, indicating the number of test cases. ($T\leq 30$) For each test case, the first line contains a string $s$, which is the string the God has. The following line contains a number $n$, the number of people’s names. Then $n$ lines follow, each with a string indicating the names. There will be no more than $10$ names in each test case, the length of string $s$ will not exceed $100,000$, and the length of each name will not exceed $100,000$. All the strings contains lowercase letters from a to z only.

Output

For each case, output Case #i: first. ($i$ is the number of the test case, from $1$ to $T$). Then output a single number, as the maximum number of the people whose name can be spelled.

Samples

2
abc
3
aa
bb
cc
aabbc
3
abc
aa
bb

Case #1: 0
Case #2: 2

Resources

The 11th UESTC Programming Contest Final