모스 부호 수열 해독

디지털 시대 이전, 무선 통신에서 가장 널리 쓰인 "이진" 부호는 모스 부호였다. 모스 부호에서 각 문자는 짧은 신호와 긴 신호(각각 점과 선)의 나열로 표현된다. 아래 표는 알파벳의 모스 부호를 나타내며, 점과 선은 각각 ASCII 문자 "."와 "-"로 표기한다.

문자 사이에 멈춤(공백)이 없으면 하나의 모스 부호 수열이 여러 가지로 해석될 수 있다. 예를 들어 수열 -.-..-- 는 CAT 로도 NXT 로도 해독될 수 있다(그 밖에도 여러 가지가 가능하다). 사람 통신사라면 언어 사전 같은 문맥 정보를 이용해 적절한 해독을 고르겠지만, 그런 사전이 주어지더라도 하나의 수열에서 여러 개의 문장을 얻을 수 있다.

각 데이터 집합에 대해 다음을 수행하는 프로그램을 작성하라.

• 하나의 모스 부호 수열과 단어 목록(사전)을 읽는다.
• 사전의 단어들만 사용하여 주어진 모스 부호 수열로부터 만들 수 있는 서로 다른 문장의 개수를 구한다.
• 그 결과를 출력한다.

여기서 문장이란 사전의 단어를 차례로 이어 붙인 수열을 뜻하며(같은 단어를 여러 번 써도 된다), 단어의 나열 순서가 다르면 서로 다른 문장으로 센다. 우리는 완전한 일치만을 센다. 즉, 모스 부호 수열 전체가 남김없이 사전의 단어들로 대응되어야 한다.

입력의 첫 줄에는 데이터 집합의 개수와 같은 양의 정수 d 가 하나 주어진다 (1 ≤ d ≤ 20). 이어서 d 개의 데이터 집합이 주어진다.

각 데이터 집합의 첫 줄에는 모스 부호 수열이 주어진다. 이는 "."와 "-"로만 이루어진, 공백이 없는 길이 10,000 이하의 비어 있지 않은 문자열이다.

둘째 줄에는 사전에 있는 단어의 개수와 같은 정수 n 이 하나 주어진다 (1 ≤ n ≤ 10,000). 이어지는 n 개의 줄에는 각각 사전의 단어가 하나씩 주어진다. 각 단어는 "A"부터 "Z"까지의 대문자로만 이루어진 길이 20 이하의 비어 있지 않은 문자열이며, 같은 단어가 사전에 두 번 이상 나오지 않는다.

출력은 정확히 d 개의 줄로 이루어진다. 각 데이터 집합마다 한 줄씩 출력한다. i 번째 줄에는 i 번째 데이터 집합의 모스 부호 수열을 분해하여 만들 수 있는 서로 다른 문장의 개수를 정수로 출력한다. 각 데이터 집합에서 이 값은 2·10^9 이하임이 보장된다.