G. Гимн Берляндии
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Берляндии невероятно богатая и славная история. Чтобы повысить уровень осведомленности о ней среди молодого поколения, Король Берляндии распорядился сочинить гимн.

Несмотря на то, что в прошлом у Берляндии было огромное множество достойных побед, есть одна наиболее важная. Король желает упомянуть ее в гимне как можно большее количество раз.

Он уже сочинил немалую часть гимна, осталось лишь заполнить некоторые места, которые ему никак не удаются. Король просит вас помочь с его работой.

Гимн Берляндии — это строка s, состоящая из не более чем 105 строчных латинских букв и знаков вопроса. Самая важная победа — это строка t, состоящая из не более чем 105 строчных латинских букв. Необходимо заменить все знаки вопроса строчными латинскими буквами так, чтобы максимизировать количество вхождений строки t в s.

Обратите внимание, что вхождения строки t в s могут пересекаться. В третьем примере рассмотрен такой случай.

Входные данные

Первая строка содержит строку из строчных латинских букв и знаков вопроса s (1 ≤ |s| ≤ 105).

Вторая строка содержит строку из строчных латинских букв t (1 ≤ |t| ≤ 105).

Произведение длин строк |s|·|t| не превосходит 107.

Выходные данные

Выведите максимальное количество вхождений строки t, которое можно достичь, заменив все знаки вопроса в строке s не строчные латинские буквы.

Примеры
Входные данные
winlose???winl???w??
win
Выходные данные
5
Входные данные
glo?yto?e??an?
or
Выходные данные
3
Входные данные
??c?????
abcab
Выходные данные
2
Примечание

В первом примере полученная строка s — "winlosewinwinlwinwin"

Во втором примере полученная строка s — "glorytoreorand". Последняя буква в строке может быть выбрана произвольно.

В третьем примере вхождения строки t пересекаются между собой. Строка s с максимальным количеством вхождений t — "abcabcab".