Saving the Universe

There is an urban legend that searching for "Google" on the Google homepage implodes the universe. It is a joke. Nothing happens if you try it.

However, in a universe far away, sending a search engine a query that is exactly that engine's own name makes the universe implode.

To prevent this, every query is pooled and handed to a central system. The system picks one search engine, sends queries to it, and can switch to another engine at any time. Queries must be processed in the order they arrive, and the system must never send a query to an engine whose name equals that query.

Switching costs money, so the number of switches has to be as small as possible. Report how many switches the central system needs when it is operated optimally.

The first line contains the number of test cases $N$. The $N$ test cases follow.

Each test case starts with a line holding the number of search engines $S$. The next $S$ lines each contain one search engine name. A name is at most 100 characters long and consists only of uppercase letters, lowercase letters, spaces, and digits. No two engines in a test case share a name.

The next line contains the number of incoming queries $Q$. The next $Q$ lines each contain one query. Every query is exactly the name of one of the search engines in that test case.

Limits

• $0 < N \le 20$
• $2 \le S \le 10$
• $0 \le Q \le 100$

For each test case, print one line in this format.

Case #X: Y

$X$ is the 1-based test case number and $Y$ is the minimum number of switches. The initial choice of a search engine does not count as a switch.

In the first example, one optimal routing starts with Dont Ask and switches to NSM after the eighth query, for a single switch.

In the second example, B9 can serve every query, so no switch happens.

A name can contain spaces, so read the input line by line.