우주 구하기 (라지)

구글 홈페이지에서 "Google"을 검색하면 우주가 붕괴한다는 도시 전설이 있다. 실제로 그런 일은 일어나지 않는다.

아주 먼 다른 우주에서는 사정이 다르다. 그곳에서는 어떤 검색 엔진에 그 검색 엔진 자신의 이름을 검색하면 정말로 우주가 붕괴한다.

그래서 그곳 사람들은 모든 질의를 한곳에 모으기로 했다. 모인 질의는 중앙 시스템으로 전달되고, 중앙 시스템이 각 질의를 어느 검색 엔진으로 보낼지 정한다. 중앙 시스템은 한 검색 엔진으로 질의를 연달아 보내다가 언제든지 다른 검색 엔진으로 바꿀 수 있다. 질의는 받은 순서대로 처리해야 하고, 이름이 질의와 같은 검색 엔진으로는 그 질의를 절대 보내면 안 된다. 전환에는 비용이 들기 때문에 전환 횟수를 최소로 줄여야 한다.

중앙 시스템을 최적으로 프로그래밍했을 때 검색 엔진을 몇 번 바꿔야 하는지 구하라.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 검색 엔진의 개수 $S$가 주어진다. 다음 $S$개 줄에는 각각 검색 엔진의 이름이 주어진다. 이름의 길이는 100자를 넘지 않고, 영어 대문자, 영어 소문자, 공백, 숫자로만 이루어진다. 한 테스트 케이스 안에 이름이 같은 검색 엔진은 없다.

그다음 줄에는 들어오는 질의의 개수 $Q$가 주어진다. 다음 $Q$개 줄에는 각각 질의가 주어진다. 각 질의는 그 테스트 케이스에 나온 검색 엔진 중 하나의 이름이다.

제한:

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

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 테스트 케이스 번호이고, $Y$는 검색 엔진 전환 횟수다. 처음에 검색 엔진을 고르는 것은 전환으로 세지 않는다.

예제 1의 첫 번째 테스트 케이스에서는 Dont Ask로 시작해서 여덟 번째 질의 뒤에 NSM으로 바꾸면 된다. 두 번째 테스트 케이스에서는 B9만 계속 써도 되므로 한 번도 바꾸지 않는다.