AlgoLiga 2018

Firma "Fraktax" potrzebuje nowego wydajnego modułu do swojego najnowszego projektu - edytora tekstu, który będzie wyszukiwał liczbę wystąpień danej frazy. Firmie zależy, aby ich edytor był wydajniejszy, niż dostępne edytory na rynku. W tej chwili został ogłoszony przetarg na napisanie właśnie takiego modułu, więc jeśli chcesz do niego przystąpić, napisz swój moduł i sprawdź czy jest on wystarczająco wydajny.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zdań do przeanalizowania (nie więcej niż 10000).

W drugim wierszu t zdań. Każde zdanie składa się z nie więcej niż 10000 znaków.

Następnie jedna liczba q - liczba zapytań (nie większa niż milion).

Każde zapytanie składa się z co najwyżej 20 znaków złożonych wyłącznie z małych lub dużych liter języka łacińskiego.

(plik z danymi do analizy nie przekracza 5 MB, żaden spójny podciąg tworzący wyraz złożony wyłącznie z małych lub dużych liter języka łacińskiego nie jest dłuższy niż 20 znaków. Znaki które mogą się pojawić: małe i duże litery języka łacińskiego, białe znaki, "?", "!", "-", ":","."  oraz ",")

Wyjście

Dla każdego zapytania liczba wystąpień szukanej frazy. Wielkość liter jest rozróżnialna.

Uwaga! Wolniejsze języki nie poradzą sobie z tym zadaniem.

Przykład

Wejście:
30
Stoi na stacji lokomotywa,
Ciezka, ogromna i pot z niej splywa:
Tlusta oliwa.
Stoi i sapie, dyszy i dmucha,
zar z rozgrzanego jej brzucha bucha:
Uch - jak goraco!
Puff - jak goraco!
Uff - jak goraco!
Wagony do niej podoczepiali
Wielkie i ciezkie, z zelaza, stali,
I pelno ludzi w kazdym wagonie,
A w jednym krowy, a w drugim konie,
A w trzecim siedza same grubasy,
Siedza i jedza tluste kielbasy,
A czwarty wagon pelen bananow,
A w piatym stoi szesd fortepianow,
W szostym armata - o! jaka wielka!
Pod kazdym kolem zelazna belka!
W siodmym debowe stoly i szafy,
W osmym sloo, niedzwiedz i dwie zyrafy,
W dziewiatym - same tuczone swinie,
W dziesiatym - kufry, paki i skrzynie,
A tych wagonow jest ze czterdziesci,
Sam nie wiem, co sie w nich jeszcze miesci.
Lecz chodby przyszlo tysiac atletow
I kazdy zjadlby tysiac kotletow,
I kazdy nie wiem jak sie wytezal,
To nie udzwigna, taki to ciezar.
Nagle - gwizd!
Brumbrumbrumbrum
10
wagon
lokomotywa
i
I
brumbrum
brum
to
czterdziesci
aa
Sam

Wyjście:
3
1
65
3
2
3
7
1
0
1