Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường

Pareidolia là một hội chứng mà mắt bạn có xu hướng nhìn thấy những thứ quen thuộc trong ảnh mà thậm chí không tồn tại (ví dụ như thấy một gương mặt trên đám mây). Nông dân John, một người với niềm yêu thương những chú bò của mình, thường xuyên thấy những thứ liên quan đến bò trong mọi vật dụng. Ví dụ, nếu như bác John thấy xâu "bqessiyexbesszieb", đôi mắt của bác sẽ tự động bỏ đi một số kí tự và nhầm lẫn thành "bessiexbessieb" - một xâu gồm \(2\) xâu con liên tiếp "bessie" (tên một cô bò mà bác rất yêu quý).

Với một xâu \(s\), ta gọi \(B(s)\) là số lượng xâu con liên tiếp "bessie" nhiều nhất có thể đạt được từ xâu \(s\) nếu xoá đi \(0\) hoặc nhiều kí tự trong xâu \(s\). Trong ví dụ trên, \(B(\)"bqessiyexbesszieb"\() = 2\).

Tính toán \(B(s)\) rất là thú vị, vì vậy bác John cho bạn một thử thách: Bạn được cho một xâu \(t\) độ dài không quá \(3 \times 10^5\) chỉ bao gồm các chữ cái in thường, hãy tính tổng \(B(s)\) cho mọi xâu con liên tiếp \(s\) của xâu \(t\).

Input

• Gồm một dòng duy nhất chứa xâu \(t\).

Output

• Gồm một dòng duy nhất chứa tổng các \(B(s)\).

Scoring

• Subtask \(1\): xâu \(t\) có độ dài không quá \(5000\).
• Subtask \(2\): Không có thêm ràng buộc.

abcdefghssijebessie

28