Нещодавно Козак Вус натрапив на наступну задачу.
Є рядок s. Треба знайти кількість підрядків цього рядка з такими властивостями:
Підрядок повинен мати принаймні 3 літери;
Усі літери підрядка однакові, за виключенням однієї.
Наприклад, рядки aab, cccdc задовільняють цим властивостям, а рядки ab, ccc, aabbaa — ні.
Рядок x є підрядком рядка y, якщо x може бути отриманим видаленням кількох (можливо, жодного або всіх) символів з початку і декількох (можливо, жодного або всіх) символів з кінця.
Допоможіть Козаку Вусу розв'язувати цю задачу.
Входные данные
Перший рядок містить рядок s (1≤∣s∣≤2⋅10
5
), який складається з літер латинської абетки нижнього регістру.
Выходные данные
Виведіть єдине число — кількість підрядків з заданими умовами.
Оценивание
Якщо рішення працює правильно при ∣s∣≤100, то воно буде оцінюватися принаймні у 15 балів.
Якщо рішення працює правильно при ∣s∣≤5000, то воно буде оцінюватися принаймні у 40 балів.