약어

약어(acronym)는 단순히 각 단어의 첫 글자만 따는 것보다 더 유연하게 만들어지기도 한다. 예를 들어 GDB는 Gnu DeBugger의 약자이다. 글자들은 각 단어에서 등장 순서를 지켜 뽑히며, 한 단어(DeBugger)가 여러 글자를 낼 수도 있다.

이 문제에서 약어는 다음 규칙으로 만든다.

1. 의미가 없는 단어(예: of, a, the)는 무시한다.
2. 각 단어에서 뽑은 글자들은 그 단어 안에서의 왼쪽에서 오른쪽 순서를 지켜야 한다.
3. 의미가 있는 모든 단어가 사용되어야 한다. 즉, 각 단어에서 적어도 한 글자를 뽑는다.

구체적으로, 의미 없는 단어를 모두 지운 뒤 남은 의미 있는 단어를 문장에 나온 순서대로 $w_1, w_2, \dots, w_k$라 하자. 약어를 이어 붙이면 약어 전체가 되는, 비어 있지 않은 $k$개의 연속한 조각 $p_1 p_2 \dots p_k$로 나누어야 하며, 각 조각 $p_i$는 단어 $w_i$의 부분수열이어야 한다. 글자는 대소문자를 구분하지 않고 비교한다(약어는 대문자, 단어는 소문자).

모든 실제 약어가 이 규칙을 따르는 것은 아니다. 예를 들어 RADAR는 "RAdio Detecting And Ranging"의 약자인데, 무시되는 단어 "and"에서 글자를 가져오므로 이 규칙으로는 만들 수 없다.

의미 없는 단어 목록과 약자, 그리고 문장이 주어질 때, 규칙에 따라 그 약자를 만들 수 있는 서로 다른 방법의 수를 구하라. 두 방법은 약어를 단어 사이에서 다르게 나누거나, 어떤 글자를 단어 안의 다른 위치에서 뽑으면 서로 다른 것으로 센다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 의미 없는 단어의 개수 $n$($1 \le n \le 100$)이 주어진다. 다음 $n$개의 줄에는 의미 없는 단어가 소문자로 하나씩 주어진다.

그 다음에는 한 개 이상의 질의 줄이 온다. 각 질의 줄에는 대문자로 된 약자와 소문자로 된 문장(소문자 단어들이 공백으로 구분된다)이 차례로 주어진다. 약자의 길이는 1 이상이며, 문장은 적어도 하나의 의미 없는 단어를 포함한다. 모든 약자와 모든 문장의 길이는 150자 이하이다. 질의 목록은 정확히 LAST CASE인 줄로 끝난다.

입력은 첫 줄이 0인 테스트 케이스로 끝난다.

각 질의에 대해, 약자를 만들 수 없으면

<약자> is not a valid abbreviation

를 출력하고, 만들 수 있으면

<약자> can be formed in i ways

를 출력한다. 여기서 i는 만들 수 있는 방법의 수이며, 32비트 부호 있는 정수 범위 안에 든다.