Booking Error

Your boss is upset. The flight to the United States that his secretary booked is wrong: he wanted a trip with as few transit stops as possible, and the booked segments do not give him that. The segments are already paid for and stay on the ticket, so he wants you, the programmer, to fix the trip by booking as few new segments as possible.

You are given every direct connection between two airports. Each connection can be flown in both directions. You are also given the segments the secretary already booked, in the order they appear on the ticket. The trip starts at the first airport of the ticket and ends at the last one.

Book the smallest number of extra segments so that your boss can travel from the start to the destination in the smallest number of segments that the direct connections allow at all.

The booked segments are flexible in timing and can be flown in any order. Your boss may fly all of them, some of them, or none of them, together with the segments you add. A segment booked from A to B can only be flown from A to B, never from B to A.

The first line contains the number of test cases $T$. ($1 \le T \le 100$) Each test case is given in $N + 2$ lines.

The first line of a test case contains the number of direct connections $N$. ($1 \le N \le 100\,000$) Each of the next $N$ lines contains the names of two different airports joined by a direct connection, which can be flown in both directions. An airport name is exactly three capital letters. Inside one test case there is at most one connection between any pair of airports.

The last line of a test case holds the faulty ticket as $M$ $A_1$ $A_2$ $\ldots$ $A_{M+1}$, where $M$ is the number of segments already booked and each $A_i$ is an airport name. Every two consecutive names mean one segment booked from the earlier airport to the later one. The bookings are faulty enough to revisit airports and even to book the same segment more than once, but every booked segment is one of the $N$ connections above. Your boss starts at $A_1$ and his destination is $A_{M+1}$.

For each test case, print on its own line the smallest number of segments that have to be booked so that, combined with the segments already booked, your boss can go from $A_1$ to $A_{M+1}$ in the smallest possible number of segments.

In the first test case of the sample, booking FRA to JFK or booking CAI to LHR lets the boss fly from CAI to JFK with one stop, which is the fewest stops possible.

In the second test case the fewest stops can only be reached along CAI, FRA, LHR, JFK. The secretary booked LHR to FRA and not the other direction, so FRA to LHR has to be booked.

In the third test case the secretary booked an optimal ticket, so nothing has to be added.