Cho xâu ký tự \(S\) chỉ gồm các chữ cái thường từ a đến z.

Một xâu đẹp được định nghĩa là một xâu con liên tiếp của \(S\) có độ dài lớn hơn hoặc bằng 4, và trong mọi đoạn con độ dài 4 của xâu đó phải có ít nhất 3 loại ký tự khác nhau.

Input

• Một dòng duy nhất chứa xâu \(S\) (độ dài không quá \(10^5\) ký tự)

Output

• Một dòng duy nhất là số lượng xâu đẹp tìm được.

Example

abcabcd

10

cbaaabacd

4

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Độ dài xâu \(S\) không quá \(100\).
• Subtask \(2\) (\(50\%\) số điểm): Độ dài xâu \(S\) không quá \(10^5\).