Amgine

Treść

Jako powszechnie wiadomo Profesor Ciekawski to jeden z najbardziej wszechstronnych naukowców jacy kiedykolwiek mieli okazje pracować na Wydziale Informatyki Politechniki Białostockiej. Swój talent wykorzystuje nie tylko do badań teoretycznych. Z jego usług nierzadko korzystają służby wywiadowcze. Biegła znajomość kryptografii pozwoliła Profesorowi na rozwiązanie niejednej zagadki. Tak jest i tym razem. Dzięki staraniom najlepszych agentów, wywiadowi udało się przechwycić jedną z najpilniej strzeżonych tajemnic wroga – maszynę szyfrującą Amgine. Teraz przyszła kolej na Profesora. Jego zadaniem jest rozpracowanie Amgine tak, aby możliwe było deszyfrowanie wrogich depesz.

Większą część pracy Profesor Ciekawski ma już za sobą. Prawie całkowicie udało mu się zrekonstruować algorytm pracy Amgine. Algorytm ten przedstawia się następująco. Przy konstruowaniu depeszy dozwolone jest korzystanie tylko i wyłącznie ze znaków odstępu i słów zawartych w książce kodowej Amgine. Po utworzeniu wiadomości wejściowej usuwane są z niej wszystkie odstępy. W ten sposób powstaje zlepek liter. Drugim krokiem szyfrowania jest zamiana liter na cyfry. Służy do tego specjalny słownik. Dla każdej z 26 liter alfabetu łacińskiego przyporządkowuje jedną z 10 cyfr. Tak zaszyfrowana depesza jest już gotowa do wysłania.

Jak zapewne się domyślasz, sposób zamiany liter na cyfry oraz usunięcie odstępów z tekstu wprowadza do wyniku pewną niejednoznaczność. Wynik taki może reprezentować wiele różnych wiadomości. Jest to ostatni element łamigłówki jaki został Profesorowi Ciekawskiemu do całkowitego złamania Amgine. Masz okazję pomóc naukowcowi w realizacji tego zadania. Napisz program, który dla podanej książki kodowej, słownika oraz zaszyfrowanej depeszy obliczy liczbę możliwych wiadomości na wejściu maszyny.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera słownik. Jest to napis składający się z 26 cyfr. Pierwsza cyfra słownika odpowiada literze A, druga literze B i tak dalej. W drugim wierszu znajduje się całkowita liczba k (1<=k<=2000) oznaczająca liczbę słów w książce kodowej. W kolejnych k wierszach podane są słowa z książki kodowej. Każde ze słów składa się wyłącznie z wielkich liter alfabetu łacińskiego, słowa nie powtarzają się, a ich łączna długość nie przekracza 20000 znaków. Ostatni wiersz zestawu danych zawiera zaszyfrowaną depeszę. Jest to napis składający się z co najwyżej 2000 cyfr.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest liczba możliwych wiadomości na wejściu Amgine. Dane wejściowe są tak dobrane, że wynik nie przekracza 10⁹.

Przykład

dane wejściowe:
2
00000011111111112222222222
4
KOT
LOT
DONOS
CI
01112
44444444444444444444444444
3
BB
A
B
444

wynik:
3
12

możliwe wiadomości na wejściu:
CI KOT
CI LOT
DONOS

A A A
A A B
A B A
A B B
B A A
B A B
B B A
B B B
A BB
BB A
B BB
BB B