空想性錯視指的是眼睛傾向於在實際上並不存在熟悉圖案的影像中看到這些圖案的現象，例如在雲朵中看到一張臉。你可以想像，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