Se da un cuvant T si K perechi de cuvinte. Fiecare cuvant al unei perechi poate contine cel mult un caracter '', care poate fi inlocuit cu orice litera mica a-z. Doua cuvinte dintr-o pereche sunt considerate la aceeasi distanta de T daca exista o modalitate de a inlocui simbolurile '' (independent, in fiecare cuvant) astfel incat distantele de editare fata de T ale celor doua cuvinte rezultate sa fie egale. Determinati pentru cate din cele K perechi este posibil acest lucru.
- Date de intrare
- Pe prima linie se citeste cuvantul T. Pe a doua linie se citeste K. Urmeaza K linii, fiecare continand doua cuvinte separate prin spatiu, reprezentand o pereche.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul de perechi valide.
- Restrictii
- 1 <= K <= 10, 1 <= lungime cuvant, lungime T <= 12, cel mult un '*' per cuvant
Exemple
Exemplul 1
Intrare
elma 6 ema alma riquelma vero dana clema fra*a rex*na fcsb steaua lmx tlma
Iesire
4
Exemplul 2
Intrare
cat 3 cat cat bat hat xy abcdefgh
Iesire
2