Це маловідомий факт, що у корів свій алфавіт - "cowphabet". Він складається з 26 літер від a' до 'z', проте порядок букв у цьому "cowphabet" може відрізнятися від стандартного порядку 'abcdefghijklmnopqrstuvwxyz'.

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

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

Зауваження: час для тестування для цього завдання подвоєний.

Формат вхідних даних

Єдиний рядок введення містить рядок літер, які почув ФН. Цей рядок має довжину від \(1\) до \(10^5\).

Формат вихідних даних

Виведіть мінімальну кількість разів, яку Мілдред сказала весь cowphabet.

Приклад вхідних даних

mildredree

Приклад вихідних даних

3

Мілдред сказала cowphabet не менше трьох разів. Це можливо, якщо cowphabet починається з mildre і ФН чув літери, які позначені великими літерами, як показано нижче.

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

ОЦІНЮВАННЯ:

• У тестах 1-5, ФН чув лише літери, які з'являються в іменах Mildred та Bessie.
• У тестах 6-16, ФН ніколи не чув жодної з літер, яка з'являється в імені Mildred.