注意：此问题的时间限制为4s，默认为2x

题目描述

Pareidolia是一种现象，你的眼睛倾向于在图像中看到熟悉的模式，而这些模式实际上并不存在——例如在云中看到一张脸。正如你可能想象的那样，由于农夫约翰经常靠近奶牛，他经常在日常用品中看到与奶牛有关的图案。例如，如果Farmer John看着字符bqessiyexbeszieb，他的眼睛会忽略一些字母，他看到的只是bessiebessie

给定字符串$s$，设B（s）表示通过从s中删除零个或多个字符可以形成的bessie的最大重复副本数

在上面的例子中，B(“bqesiyexbesszieb”）=2.

计算B（s）是一个有趣的挑战，但Farmer John对解决一个更有趣的挑战感兴趣：给定字符串$t$长度最多为$3·10^5$仅由字符a-z组成，在所有连续子字符串上计算B（s）的和.

输入格式

输入由一个长度不超过$3·10^5$的非空字符串组成

其字符均为小写英文字母。

输出格式

输出单个数字，即可以在输入字符串的所有子字符串中生成的bessie的总数。

bessiebessie

14

12个子字符串正好包含1个bessie，1个字符串正好包含2个bessie，因此总数为12·1+1·2=14

abcdefghssijebessie

28

数据范围

对于测试点3-5：字符串的长度最多为5000。

对于测试点6-12：无额外限制。