III Mistrzostwa Wielkopolski w Programowaniu Zespołowym 2-3 grudnia 2005
Zadanie J. Telefony

Opis

W MWPZtowie, po rozbudowie sieci komórkowej, a także ogólnej teleinformatyzacji kraju, pojawiła się potrzeba, aby upraszczać numery telefonów. Wszelkiego rodzaju firmy, instytucje, urzędy itp. chciałyby mieć jak najprostszy numer, aby klienci mogli go jak najłatwiej zapamiętać. Do Urzędu Telekomunikacji trafiło całe mnóstwo podań o przydział tzw. „prostego numeru” jak np. 700123456, czy 987654321. Niestety podań jest o wiele więcej niż dostępnych numerów, które w tak prosty sposób można by zapamiętać. Urząd nie chce zawieść swoich petentów i przydzielać im byle jakich numerów. Chciałby każdego zadowolić, chyba, że jest to niemożliwe. Zlecił Ci więc napisanie programu, który porozdziela te proste numery i usatysfakcjonuje wszystkich.

Oczywiście, łatwo było zauważyć, że nie da się zadowolić dużej grupy klientów małą ilością numerów, tak, żeby każdy miał inny numer telefonu. Gdy przedstawiono ten problem Ministrowi Telekomunikacji, zadecydował on, że pewna część instytucji dostanie dokładnie to, o co prosiła, zgodnie z kolejnością zgłoszeń, a dla następnych trzeba wymyślić coś, co też im jakoś będzie odpowiadać. Na początku nie było jeszcze wiadomo co to będzie. Pomysły na odesłanie im odmowy wraz z czekoladką, czy inne tego typu, szybko upadły. Ale pojawił się nowy pomysł! Otóż numery, których używają obecnie można przecież, w dobie gdy już praktycznie ze wszystkich telefonów można pisać smsy, zamienić na słowa! Jest to pomysł tym lepszy, że właśnie Urząd wprowadził na rynek nowe rodzaje telefonów, które uwzględniają tylko znaki używane w języku MWPZ. Nowy rozkład literek to:

        1 - a,b
        2 - c,d
        3 - e,f,g
        4 - h,i,j
        5 - k,l
        6 - m,n
        7 - o,p
        8 - r,s
        9 - t,u
        0 - w,y,z
      

Czyli np. numer 93533760 można zamienić na słowo telefony i w ten sposób reklamować swój numer telefonu.

Twoim zadaniem będzie napisanie programu, który dla listy słów, które Urząd zgodził się akceptować w numerach, oraz listy numerów wyliczy, na ile sposobów można zakodować każdy z numerów telefonu przy użyciu danych słów. Oczywiście słowa mogą być różnej długości i niektóre numery mogą składać się z kilku słów. W takim przypadku, dla większej czytelności pomiędzy każdymi dwoma słowami trzeba zostawić co najmniej jedną cyfrę z numeru, która będzie rozdzielała dwa słowa używane do zakodowania numeru. Dla zwiększenia czytelności Urząd zadecydował także, że do kodowania jednego numeru nie można nigdy użyć dwa razy tego samego słowa. Numer możemy za to kodować dowolną mieszanką pełnych słów i cyfr, pod warunkiem, że spełnione są wcześniejsze założenia. Oczywiście, jeśli w numerze nie znajduje się taki podciąg cyfr, żeby dopasować do niego jakiekolwiek słowo, można go zakodować na jeden sposób, gdyż wypisanie wprost numeru jest także sposobem podania go klientom.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. W pierwszej linii zestawu znajduje się liczba M (0 ≤ M ≤ 10000) oznaczającą liczbę słów, które Urząd zaakceptował. W kolejnych M liniach znajdują się w każdej linii jedno słowo składające się tylko i wyłącznie ze znaków, które istnieją w języku MWPZ (są to litery języka łacińskiego występujące w alfabecie polskim) oraz znaku nowej linii po nim. Długość słowa nie przekracza 10 znaków, a każde słowo składa się z co najmniej jednego znaku. Wśród tych M słów nie istnieją dwa identyczne. Po liście słów, w kolejnej linii znajdują się dwie liczby całkowite N i L (0 ≤ N ≤ 500; 1 ≤ L ≤ 9) oznaczające odpowiednio ilość numerów, które trzeba zakodować oraz ilość cyfr, z których składa się numer telefonu w MWPZtowie. W kolejnych N liniach znajdują się numery telefonów - każdy numer w jednej, osobnej linii. Każdy numer telefonu w MWPZtowie składa się zawsze z takiej samej ilości L cyfr.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać w osobnej linii jedną liczbę całkowitą oznaczającą, na ile sposobów można zapisać dany numer zgodnie z zasadami przyjętymi przez Urząd Telekomunikacji.

Przykład

Wejście

2
3
ala
ma
kota
3 9
151615791
151515161
123456789
2
a
az
3 9
111111111
122110221
101010101

Wyjście

5
7
1
10
8
22

Wyjaśnienie przykładu pierwszego:

W rozwiązaniu policzymy:

możliwości zakodowania numeru 151615791:

151615791, ala615791, 151ma791, 15161kota, ala61kota

(nie może być alamakota, bo pomiędzy wyrazami „ala” i „ma” nie ma cyfry przerwy)

możliwości zakodowania numeru 151515161:

151515161, ala515161, 15ala5161, 1515ala61, 151515ma, ala5151ma, 15ala51ma

możliwości zakodowania numeru 123456789:

123456789