Historyjka.
Zadanie Do rozwiązania jest klasyczne zadanie. Dany jest tekst o długości n oraz wzorzec o długości m. Należy znaleźć liczbę wystąpień wzorca w tekście.
Tekst składa się z małych liter alfabetu łacińskiego. Wzorzec składa się z małych liter alfabetu łacińskiego, ale może w nim wystąpić (co najwyżej jeden) symbol '?'. Uznajemy, że '?' dopasowuje się poprawnie do każdej litery.
W pierwszej linii znajduje się liczba naturalna T (1 ≤ T ≤ 20) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.
Pojedynczy zestaw testowy zbudowany jest następująco:
w pierwszej linii zapisany jest tekst o długości n (1 ≤ n ≤ 105) złożony z małych liter alfabetu łacińskiego, w drugiej linii zapisany jest wzorzec o długości m (1 ≤ m ≤ n) złożony z małych liter alfabetu łacińskiego i co najwyżej jednego symbolu '?'.
Dla każdego zestawu testowego należy w osobnej linii wypisać liczbę wystąpień wzorca w tekście.
Dla danych wejściowych
3
aaaaabbb
ab
aaaaabbb
a?
aaaa
b
poprawną odpowiedzią jest
1
5
0