깨진 메일

Gagan은 친구 Jorge에게서 메일을 한 통 받았다. 중요한 내용이 담긴 메일인데 전송 도중에 망가졌다. 공백이 모두 사라졌고, 공백이 사라진 뒤에 일부 글자가 다른 글자로 바뀌었다. 지금 Gagan에게 남은 것은 소문자로만 이루어진 문자열 $S$ 하나뿐이다.

원래 메일은 아래에서 설명하는 사전의 단어를 이어 붙여 만들었다. 글자가 바뀐 시점은 공백이 사라진 뒤이고, 바뀐 글자 두 개의 위치 차이는 항상 $5$ 이상이다. 예를 들어 "code jam"은 "codejam", "dodejbm", "zodejan", "cidejab"이 될 수 있지만 "kodezam"은 될 수 없다. "k"로 바뀐 위치와 "z"로 바뀐 위치의 차이가 $4$밖에 되지 않기 때문이다.

바뀐 글자는 최소 몇 개인가?

사전에는 소문자 $1$자 이상 $10$자 이하인 단어가 $W$개 들어 있고, 입력 맨 앞에 주어진다. 자연어 사전은 아니지만 영어 단어도 일부 들어 있다. 사전은 입력 하나에 한 번만 주어지고, 모든 테스트 케이스가 같은 사전을 쓴다. 사전은 사전순으로 증가하는 순서로 주어지며 같은 단어가 두 번 나오지 않는다.

첫째 줄에 사전에 든 단어의 개수 $W$가 주어진다. 다음 $W$개 줄에 사전의 단어가 소문자 a부터 z로 이루어진 문자열로 한 줄에 하나씩 주어진다. 그다음 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어지며, 각 테스트 케이스는 소문자 a부터 z로 이루어진 문자열 $S$ 한 줄이다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 $1$부터 시작하는 테스트 케이스 번호이고, y는 $S$를 만드는 동안 바뀐 글자 개수의 최솟값이다.

• $1 \le W \le 5000$
• 사전의 각 단어는 소문자 $1$자 이상 $10$자 이하이다.
• 사전은 사전순으로 증가하는 순서로 주어진다.
• 사전에 같은 단어가 두 번 나오지 않는다.
• 사전에 든 글자 수의 합은 $30000$ 이하이다.
• $1 \le T \le 4$
• $1 \le |S| \le 4000$
• $S$는 위에서 설명한 방법으로 만들 수 있는 문자열이다.

사전은 자연어 사전이 아니므로 영어 단어라고 해서 반드시 들어 있지는 않다. 사전에 "operation"과 "oo"는 있고 "cooperation"은 없을 수 있다. 그러면 "cooperation"처럼 보이는 구간도 사전에 있는 단어로만 나누어 읽어야 한다.