외계 언어 (대규모)

연구진이 먼 행성에서 보내온 외계 언어를 해독했다. 이 언어의 단어는 모두 소문자 $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 15$
• $1 \le D \le 5000$
• $1 \le N \le 500$

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

Case #X: K

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