空想性错视指的是眼睛倾向于在实际上并不存在熟悉图案的图像中看到这些图案的现象，例如在云朵中看到一张脸。你可以想象，Farmer John 总是与奶牛相处，因此经常在日常物品中看到与奶牛有关的图案。例如，看着字符串 "bqessiyexbesszieb" 时，Farmer John 的眼睛会忽略一些字母，只看到 "bessiebessie"。

给定字符串 $s$，令 $B(s)$ 表示从 $s$ 中删除零个或更多字符后，能形成的连续重复的 "bessie" 的最大份数。在上面的例子中，$B(\texttt{bqessiyexbesszieb}) = 2$。

计算 $B(s)$ 是一个有趣的挑战，但 Farmer John 想解决一个更加有趣的挑战：给定一个长度不超过 $3\cdot 10^5$、只包含字符 a-z 的字符串 $t$，计算 $t$ 的所有连续子串 $s$ 的 $B(s)$ 之和。

输入格式

输入为一个非空字符串，长度不超过 $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