영어 읽기

인터넷에서 다음과 같은 문장을 본 적이 있을 수 있다.

It is itnersetnig taht pepole can raed smoe grabeld wrods.

원래 문장은 'It is interesting that people can read some garbled words'이다. 각 단어는 첫 글자와 마지막 글자를 제외한 가운데 글자들의 순서가 섞여 있다. 영어 단어를 알고 있다면 첫 글자와 마지막 글자가 같고, 그 사이 글자들의 multiset이 같을 때 가운데 글자의 순서가 달라도 단어를 읽는 데 큰 문제가 없다고 하자.

따라서 한 단어가 여러 사전 단어로 해석될 수 있다. 예를 들어 abcde는 abcde, abdce, acbde, acdbe, adbce, adcbe와 같이 첫 글자와 마지막 글자가 같고 가운데 글자들의 구성이 같은 단어들로 해석될 수 있다. 단, 해석 결과는 사전에 실제로 들어 있는 단어만 인정한다.

영어 문장이 주어졌을 때, 각 단어를 사전에 있는 단어로 해석하는 방법의 수를 구하라. 문장은 하나 이상의 단어로 이루어지며, 단어들은 공백 하나로 구분된다.

첫째 줄에 사전에 있는 단어의 수 N(0 <= N <= 10,000)이 주어진다. 다음 N개의 줄에는 사전에 있는 영어 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 100자를 넘지 않는다.

그다음 줄에 해석할 문장의 수 M(0 <= M <= 10,000)이 주어진다. 다음 M개의 줄에는 해석할 영어 문장이 한 줄에 하나씩 주어진다. 각 문장의 길이는 10,000자를 넘지 않는다.

영어 단어는 알파벳 대문자와 소문자로만 이루어지며, 대소문자는 서로 다른 문자로 취급한다.

각 문장마다 해석하는 방법의 수를 한 줄에 하나씩 출력한다. 정답은 32-bit signed int 범위 안에 있다고 가정한다.