La pareidolia è il fenomeno per cui gli occhi tendono a vedere forme familiari in immagini in cui in realtà non esistono, ad esempio un volto in una nuvola. Come puoi immaginare, dato che Farmer John è costantemente vicino alle mucche, vede spesso forme legate alle mucche negli oggetti di tutti i giorni. Ad esempio, se guarda la stringa "bqessiyexbesszieb", i suoi occhi ignorano alcune lettere e vede soltanto "bessiebessie".

Data una stringa $s$, sia $B(s)$ il numero massimo di copie ripetute di "bessie" che si possono formare eliminando zero o più caratteri da $s$. Nell'esempio sopra, $B(\texttt{bqessiyexbesszieb}) = 2$.

Calcolare $B(s)$ è una sfida interessante, ma Farmer John vuole risolverne una ancora più interessante: data una stringa $t$ di lunghezza al massimo $3\cdot 10^5$, composta soltanto dai caratteri a-z, calcola la somma di $B(s)$ su tutte le sottostringhe contigue $s$ di $t$.

Input

L'input consiste in una stringa non vuota di lunghezza al massimo $3\cdot 10^5$, i cui caratteri sono tutti lettere inglesi minuscole.

Output

Stampa un solo numero: il numero totale di copie di "bessie" che si possono formare su tutte le sottostringhe della stringa di input.

Esempi

Input 1

bessiebessie

Output 1

14

Nota

Dodici sottostringhe contengono esattamente 1 "bessie", e 1 stringa contiene esattamente 2 copie di "bessie", quindi il totale è $12\cdot 1 + 1 \cdot 2 = 14$.

Input 2

abcdefghssijebessie

Output 2

28

Sottoproblemi

• Input 3-5: la stringa ha lunghezza al massimo $5000$.
• Input 6-12: nessun vincolo aggiuntivo.

Autori del problema: Brandon Wang e Benjamin Qi