Saving the Universe (Large)

An urban legend says that if you open the Google homepage and search for "Google", the universe implodes. It does not.

In a universe far away the rule is different. There, searching a search engine for that same search engine's name really does make the universe implode.

To stay safe, the people there pool every query. The pooled queries go to a central system, and the central system decides which search engine each query is sent to. The central system sends a run of queries to one search engine and can switch to another search engine at any time. Queries must be processed in the order they arrive, and the central system must never send a query to the search engine whose name equals that query. Switching costs money, so the number of switches has to be as small as possible.

Find how many times the central system has to switch search engines when it is programmed optimally.

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

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

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

Limits:

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

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

Case #X: Y

$X$ is the test case number and $Y$ is the number of search engine switches. Do not count the initial choice of a search engine as a switch.

In the first test case of example 1, you can start with Dont Ask and switch to NSM after the eighth query. In the second test case you can stay on B9 the whole time, so no switch happens.