우주를 지키는 검색 라우팅

구글 홈페이지에서 "구글"을 검색하면 우주가 붕괴한다는 이야기가 있다. 물론 농담이다. 검색해 봐도 아무 일도 일어나지 않는다.

하지만 어떤 먼 우주에서는 검색 엔진에 그 엔진의 이름과 똑같은 질의를 보내면 우주가 붕괴한다.

사람들은 이 사고를 막으려고 모든 질의를 한곳에 모아 중앙 시스템에 넘긴다. 중앙 시스템은 검색 엔진 하나를 골라 질의를 보내고, 언제든 다른 엔진으로 바꿀 수 있다. 질의는 받은 순서대로 처리해야 하며, 질의와 이름이 같은 엔진에는 절대 그 질의를 보낼 수 없다.

비용을 줄이려면 엔진을 바꾸는 횟수가 가장 적어야 한다. 중앙 시스템을 최적으로 운영할 때 엔진을 몇 번 바꾸어야 하는지 구하라.

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

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

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

제한

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

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

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 검색 엔진을 바꾸는 최소 횟수다. 처음에 엔진을 고르는 것은 바꾼 횟수에 넣지 않는다.

첫 번째 예제에서는 Dont Ask로 시작해서 여덟 번째 질의를 처리한 뒤 NSM으로 바꾸면 한 번만 바꾸어도 된다.

두 번째 예제에서는 B9 하나로 모든 질의를 처리할 수 있어서 한 번도 바꾸지 않는다.

이름에 공백이 들어갈 수 있으므로 입력은 줄 단위로 읽어야 한다.