외계 언어

수년간의 연구 끝에, Google Labs의 과학자들은 머나먼 행성에서 전송된 외계 언어를 발견했다. 이 외계 언어는 모든 단어가 정확히 L개의 소문자로 이루어져 있다는 점에서 매우 독특하다. 또한, 이 언어에는 정확히 D개의 단어가 있다.

외계 언어의 모든 단어를 담은 사전을 구축한 뒤, 과학자들은 외계인들이 지난 십 년 동안 지구로 메시지를 전송해 왔다는 사실을 발견하는 다음 돌파구를 마련했다. 안타깝게도 두 행성 사이의 거리 때문에 이러한 신호가 약해져 일부 단어가 잘못 해석될 수 있다. 이 메시지들을 해독하는 데 도움을 주기 위해, 과학자들은 주어진 패턴에 대해 가능한 해석의 수를 구하는 알고리즘을 고안해 달라고 요청했다.

패턴은 정확히 L개의 토큰으로 이루어진다. 각 토큰은 하나의 소문자(과학자들은 이 글자가 맞다고 매우 확신한다)이거나, 괄호 ( 와 )로 둘러싸인 서로 다른 소문자들의 묶음이다. 예를 들어, (ab)d(dc)는 첫 번째 글자가 a 또는 b이고, 두 번째 글자는 확실히 d이며, 마지막 글자는 d 또는 c임을 뜻한다. 따라서 패턴 (ab)d(dc)는 다음 4가지 가능성 중 어느 하나를 나타낼 수 있다: add, adc, bdd, bdc.

제한

테스트 세트당 시간 제한: 20초. 메모리 제한: 1 GB.

소규모 데이터 세트

1 ≤ L ≤ 10 1 ≤ D ≤ 25 1 ≤ N ≤ 10

대규모 데이터 세트

1 ≤ L ≤ 15 1 ≤ D ≤ 5000 1 ≤ N ≤ 500

입력의 첫 번째 줄에는 공백으로 구분된 3개의 정수 L, D, N이 주어진다. 이어지는 D개의 줄에는 각각 길이가 L인 단어 하나가 주어진다. 이 단어들은 외계 언어에 존재한다고 알려진 단어들이다. 그다음 N개의 테스트 케이스가 각각 별도의 줄에 주어지며, 각 테스트 케이스는 위에서 설명한 패턴으로 이루어진다. 주어지는 알려진 모든 단어는 서로 다르다고 가정해도 된다.

각 테스트 케이스에 대해 다음을 출력한다.

Case #X: K

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, K는 외계 언어에서 패턴과 일치하는 단어의 수를 나타낸다.