외계어 (작은 입력)

연구진이 먼 행성에서 보내온 외계어를 해독했다. 이 언어의 단어는 모두 정확히 L개의 소문자로 이루어지고, 사전에 실린 단어는 정확히 D개다.

사전을 다 만든 뒤, 연구진은 외계인이 지난 10년 동안 지구로 신호를 보내왔다는 사실을 알아냈다. 두 행성 사이의 거리 때문에 신호가 약해져서 일부 글자는 잘못 읽힐 수 있다. 그래서 주어진 패턴을 몇 가지로 해석할 수 있는지 세는 프로그램이 필요하다.

패턴은 정확히 L개의 토큰으로 이루어진다. 각 토큰은 소문자 한 글자이거나, 서로 다른 소문자 여러 개를 괄호 (와 )로 감싼 묶음이다. 한 글자짜리 토큰은 그 자리의 글자가 확실하다는 뜻이고, 묶음은 그 자리의 글자가 묶음 안의 글자 중 하나라는 뜻이다. 예를 들어 (ab)d(dc)는 첫 글자가 a 또는 b, 둘째 글자가 d, 셋째 글자가 d 또는 c라는 뜻이므로 add, adc, bdd, bdc 네 가지를 나타낸다.

패턴마다 사전의 단어 중 그 패턴과 맞는 단어가 몇 개인지 구하라.

첫 줄에 정수 L, D, N이 공백으로 구분되어 주어진다. 다음 D개의 줄에는 길이가 L인 단어가 한 줄에 하나씩 주어진다. 이 단어는 외계어에 실제로 있다고 알려진 단어이며 모두 서로 다르다. 이어서 N개의 줄에 패턴이 한 줄에 하나씩 주어진다.

제한

• $1 \le L \le 10$
• $1 \le D \le 25$
• $1 \le N \le 10$

패턴마다 다음 형식으로 한 줄씩 출력한다.

Case #X: K

X는 패턴의 번호로 1부터 시작하고, K는 그 패턴과 맞는 사전 단어의 개수다.