깨진 이메일

Gagan은 방금 친구 Jorge에게서 이메일을 받았다. 이메일에는 중요한 정보가 들어 있지만, 안타깝게도 전송되는 도중 손상되었다. 모든 공백이 사라졌으며, 공백이 제거된 뒤 일부 문자가 다른 문자로 바뀌었다! 현재 Gagan에게 남은 것은 소문자로 이루어진 문자열 S뿐이다.

이 이메일이 원래 아래에 설명된 사전의 단어들로 구성되었다는 것을 알고 있다. 또한 공백이 제거된 뒤 문자들이 바뀌었으며, 문자가 바뀐 임의의 두 위치의 인덱스 차이가 5보다 작지 않다는 것도 알고 있다. 예를 들어 문자열 "code jam"은 "codejam", "dodejbm", "zodejan" 또는 "cidejab"이 될 수 있지만, "kodezam"이 될 수는 없다. 이는 "k" 번째 변경과 "z" 번째 변경의 인덱스 사이 거리가 4에 불과하기 때문이다.

바뀌었을 수 있는 문자의 최소 개수는 얼마인가?

사전

사전에는 소문자 문자가 적어도 1개, 최대 10개인 단어 W개가 들어 있으며, 입력 파일의 시작 부분에 주어진다. 이 사전은 어떠한 자연어의 사전도 아니지만, 일부 영어 단어가 들어 있기는 하다. 하나의 입력 파일에 있는 모든 테스트 케이스에서 동일한 사전을 사용한다. 사전은 사전순 오름차순으로 주어지며 중복된 단어를 포함하지 않는다.

제한

메모리 제한: 1GB. W = 521196. 사전의 각 단어는 소문자 문자를 적어도 1개, 최대 10개 포함한다. 사전은 사전순 오름차순으로 정렬되어 있다. 사전에는 중복된 단어가 없다. 사전에 있는 문자의 총개수는 3323296이다. S는 유효하다. 즉, 위에서 설명한 방법으로 S를 만드는 것이 가능하다.

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

시간 제한: 30초. 1 ≤ T ≤ 20. 1 ≤ 길이 S ≤ 50.

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

시간 제한: 60초. 1 ≤ T ≤ 4. 1 ≤ 길이 S ≤ 4000.

입력의 첫 줄에는 사전에 있는 단어의 수 W가 주어진다. 다음 W개의 각 줄에는 사전의 단어를 나타내는 소문자 문자열 a-z이 주어진다. 입력의 다음 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 소문자로 이루어진 문자열 S a-z가 담긴 한 줄로 구성된다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 S를 만들기 위해 바뀌었을 수 있는 문자의 최소 개수이다.

설명

"code"와 "jam"는 모두 사전에 등장한다. "cooperation"는 영어 단어이지만 사전에 등장하지 않고, "aabea"는 등장한다.

문제 설명에 예제 케이스가 보이도록 하기 위해, 예제 케이스의 사전 크기는 제한 조건을 만족하지 않는다는 점에 유의한다.