Giải bài trực tuyến

Đề bài tương tự bài "Chuỗi hạt" (NKNL) nhưng có giới hạn lớn hơn.

Như ta biết, một chuỗi hạt có thể được xâu từ rất nhiều hạt ngọc màu sắc khác nhau. Để tiện lợi, ta dùng các chữ cái in thường để mô tả các màu sắc: chẳng hạn chữ a mô tả màu đỏ, chữ b mô tả màu xanh, v.v.. Các hạt ngọc có thể có 26 màu khác nhau tương ứng với 26 chữ cái in thường. Như vậy, một chuỗi hạt có thể được biểu diễn bởi một xâu ký tự gồm các chữ cái in thường, mỗi ký tự mô tả màu của các hạt ngọc theo chiều kim đồng hồ bắt đầu từ một hạt ngọc nào đó.

Tuy nhiên, do chuỗi hạt có dạng vòng tròn, nên có thể có những chuỗi ký tự khác nhau cùng biểu diễn một chuỗi hạt, chẳng hạn bacade và cadeba có thể cùng biểu diễn chuỗi hạt. Để tránh tình trạng này, ta quy định trong các chuỗi ký tự cùng thể hiện một chuỗi hạt, ta chỉ sử dụng chuỗi ký tự có thứ tự từ điển nhỏ nhất để biểu diễn chuỗi hạt đó. Như vậy với chuỗi hạt ở ví dụ nêu trên chỉ biểu diễn bằng chuỗi acadeb.

Để đảm bảo tính thẩm mỹ, mỗi chuỗi hạt cần có ít nhất 5 hạt ngọc.

Yêu cầu: Cho một chuỗi ký tự S gồm các chữ cái in thường. Nhiệm vụ của bạn là đếm xem có bao nhiêu chuỗi con gồm các ký tự liên tiếp của S có thể biểu diễn một chuỗi hạt nào đó.

Input

Chuỗi ký tự S, gồm các chữ cái in thường (độ dài không quá 1000).

Output

Ghi ra một số nguyên duy nhất là số chuỗi con gồm các ký tự liên tiếp của S có thể biểu diễn một chuỗi hạt nào đó.

Example

Input:
absdcabd

Output:
1

Giải thích
Chỉ duy nhất 1 chuỗi hạt là : absdc