У Берляндии невероятно богатая и славная история. Чтобы повысить уровень осведомленности о ней среди молодого поколения, Король Берляндии распорядился сочинить гимн.
Несмотря на то, что в прошлом у Берляндии было огромное множество достойных побед, есть одна наиболее важная. Король желает упомянуть ее в гимне как можно большее количество раз.
Он уже сочинил немалую часть гимна, осталось лишь заполнить некоторые места, которые ему никак не удаются. Король просит вас помочь с его работой.
Гимн Берляндии — это строка s, состоящая из не более чем 105 строчных латинских букв и знаков вопроса. Самая важная победа — это строка t, состоящая из не более чем 105 строчных латинских букв. Необходимо заменить все знаки вопроса строчными латинскими буквами так, чтобы максимизировать количество вхождений строки t в s.
Обратите внимание, что вхождения строки t в s могут пересекаться. В третьем примере рассмотрен такой случай.
Выходные данные
Выведите максимальное количество вхождений строки t, которое можно достичь, заменив все знаки вопроса в строке s не строчные латинские буквы.
Примечание
В первом примере полученная строка s — "winlosewinwinlwinwin"
Во втором примере полученная строка s — "glorytoreorand". Последняя буква в строке может быть выбрана произвольно.
В третьем примере вхождения строки t пересекаются между собой. Строка s с максимальным количеством вхождений t — "abcabcab".