Это малоизвестный факт, что у коров свой алфавит - "cowphabet". Он состоит из 26 букв от 'a' до 'z', однако порядок букв в этом "cowphabet" может отличаться от стандартного порядка 'abcdefghijklmnopqrstuvwxyz'.

Коротая время, Милдред бормочет cowphabet опять и опять. Фермер Нхой хочет узнать, сколько раз она пробормотала cowphabet.

По заданной строке букв, которые услышал ФН, вычислите минимальное количество раз, которое Милдред пробормотала весь cowphabet. ФН мог не услышать некоторые из букв, которые бормотала Милдред.

Замечание: время на тест для этой задачи удвоено.

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

Единственная строка ввода содержит строку маленьких букв, которые услышал ФН. Эта строка имеет длину от 1 до 105.

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

Выведите минимальное количество раз, которое Милдред произнесла весь cowphabet.

Пример

Милдред произнесла cowphabet не менее трёх раз. Это возможно, если cowphabet начинается с mildre и ФН слышал буквы, которые помечены заглавными буквами, как показано ниже.

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz