우주 구하기

도시 전설에 따르면 Google 홈페이지에 접속해 "Google"을 검색하면 우주가 내파한다고 한다. 비밀 하나를 알려 주겠다... 사실이다! 시도하거나 누구에게도 말하지 말라. 알겠다, 사실이 아닐 수도 있다. 그저 농담이다.

아주아주 먼 우주에서는 그렇지 않다. 그 우주에서는 어떤 검색 엔진에서든 그 검색 엔진의 이름을 검색하면 우주가 정말 내파한다!

이를 막기 위해 사람들은 흥미로운 해결책을 생각해 냈다. 모든 질의를 한데 모은다. 질의들은 어떤 질의를 어떤 검색 엔진으로 보낼지 결정하는 중앙 시스템으로 전달된다. 중앙 시스템은 일련의 질의를 하나의 검색 엔진으로 보내며, 언제든 다른 검색 엔진으로 전환할 수 있다. 질의는 수신된 순서대로 처리해야 한다. 중앙 시스템은 이름이 질의와 일치하는 검색 엔진으로 그 질의를 절대 보내서는 안 된다. 비용을 줄이기 위해 전환 횟수를 최소화해야 한다.

중앙 시스템을 최적으로 프로그래밍한다고 가정할 때 검색 엔진 사이를 몇 번 전환해야 하는지 구하는 것이 과제이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 0 < N ≤ 20

작은 데이터 세트(테스트 세트 1 - 공개)

2 ≤ S ≤ 10 0 ≤ Q ≤ 100

큰 데이터 세트(테스트 세트 2 - 비공개)

2 ≤ S ≤ 100 0 ≤ Q ≤ 1000

입력 파일의 첫 줄에는 케이스 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 케이스는 검색 엔진의 수 S로 시작한다. 다음 S개의 줄에는 각각 검색 엔진의 이름이 주어진다. 각 검색 엔진 이름의 길이는 백 자 이하이며, 대문자, 소문자, 공백, 숫자로만 구성된다. 이름이 같은 두 검색 엔진은 주어지지 않는다.

그다음 줄에는 들어오는 질의의 수 Q가 주어진다. 다음 Q개의 줄에는 각각 질의가 주어진다. 각 질의는 해당 케이스에 있는 검색 엔진의 이름이다.

각 입력 케이스에 대해 다음을 출력한다.

Case #X: Y

여기서 X는 테스트 케이스 번호이고 Y는 검색 엔진 전환 횟수이다. 처음 검색 엔진을 선택하는 것은 전환으로 세지 않는다.

첫 번째 케이스에서 가능한 한 가지 방법은 Dont Ask를 사용하기 시작해 질의 번호 8 뒤에 NSM(으)로 전환하는 것이다. 두 번째 케이스에서는 B9(을)를 사용하면 전환할 필요가 없다.