Парейдолия — явление, при котором глаза склонны видеть знакомые образы там, где их на самом деле нет, например лицо в облаке. Как нетрудно представить, Farmer John постоянно находится рядом с коровами и потому часто видит связанные с ними образы в повседневных предметах. Например, глядя на строку "bqessiyexbesszieb", Farmer John игнорирует некоторые буквы и видит только "bessiebessie".

Для строки $s$ обозначим через $B(s)$ максимальное число повторяющихся подряд копий "bessie", которые можно получить, удалив ноль или более символов из $s$. В примере выше $B(\texttt{bqessiyexbesszieb}) = 2$.

Вычисление $B(s)$ — интересная задача, но Farmer John хочет решить ещё более интересную: для строки $t$ длины не более $3\cdot 10^5$, состоящей только из символов a-z, вычислить сумму $B(s)$ по всем непрерывным подстрокам $s$ строки $t$.

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

Входные данные содержат непустую строку длины не более $3\cdot 10^5$, все символы которой — строчные английские буквы.

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

Выведите одно число — общее количество копий "bessie", которые можно получить по всем подстрокам входной строки.

Примеры

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

bessiebessie

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

14

Примечание

Двенадцать подстрок содержат ровно 1 "bessie", а 1 строка содержит ровно 2 копии "bessie", поэтому сумма равна $12\cdot 1 + 1 \cdot 2 = 14$.

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

abcdefghssijebessie

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

28

Подзадачи

• Входные данные 3-5: длина строки не превышает $5000$.
• Входные данные 6-12: дополнительных ограничений нет.

Авторы задачи: Brandon Wang и Benjamin Qi